Junyuan's Homepage

203. 移除链表元素

题目链接：click here
文章讲解：click here
给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
思路：
这道题是基础的链表删减指定元素操作，要求返回最终的头节点。

容易想到边界条件：若头节点本身等于 val，则头节点会产生变化。这样就引入了额外的特殊处理逻辑。

可以使用虚头节点技术，额外引入一个虚拟的头，指向链表的真正的头，后续就可以以相同的策略进行链表遍历和删减了。

遍历：iter 迭代器从虚头节点开始，每次移动前需要检查后一节点是否存在且是否为 val，若不存在，则说明遍历结束；若为 val，则需要删除，删除就简单的进行节点跨链接即可；若都不是，则迭代器移动到下一节点，如此循环直到遍历结束。

代码：

class Solution
{
public:
    ListNode *removeElements(ListNode *head, int val)
    {
        ListNode vhead(0, head);
        ListNode *now_item = &vhead;
        while (now_item->next)
        {
            if (now_item->next->val == val)
            {
                auto kid = now_item->next->next;
                delete now_item->next;
                now_item->next = kid;
            }
            else
            {
                now_item = now_item->next;
            }
        }

        return vhead.next;
    }
};

细节：
- 由于Node类定义里next是普通指针，其对象是new出来的，故而内存需要手动使用 delete 删除，这个点我是忽略了的。

707. 设计链表

题目链接：click here
文章讲解：click here
题目描述：简而言之，实现一个具有按索引查找、头尾部插入、特定索引位置前插入、删除特定索引的链表
思路：
- 完整地实现链表的增删查操作：
  - 增包括头尾增加、特定位置前插入：
    需要考虑特殊情况：头部切换(使用虚拟头节点可以避免)、传入特定位置的索引是否有效，需要记录当前链表总长度来快速判断
    注意合法的增操作后要更新链表长度
    
    具体的，只需要实现特定位置前插入这个功能即可，头插入和尾插入都可以调用这个接口，分别输入索引为0和当前链表的size即可。
    首先判断输入的索引 i 是否超出尺寸，未超出，则可执行对应的增操作
    根据 链表遍历式 ，遍历到索引为 i-1 和索引为 i 的节点
    new 一个新节点出来，其next指向 i 节点，然后让 i-1 节点的next 指向该新节点。
    这里由于使用了虚拟头节点， i 即使为 0，也是没有问题的，此时本质上是插入了新的头节点。
  - 删包括特定位置删除
    和增操作类似的，三种情况：删头、删尾、删中间，都可以统一到链表遍历式里。
    注意合法的删操作后要更新链表长度
    
    具体的，若索引 i 小于链表长度，则可以执行对应的删操作
    根据 链表遍历式 ，遍历到索引为 i-1 和索引为 i 的节点
    记录 i 节点的next 为 kid，删 i 节点，i-1 节点的 next 指向 kid。
    这里由于使用了虚拟头节点， i 即使为 0，也是没有问题的，此时本质上是删除了头节点。
  - 查包括查看对应索引节点的存储内容
    也需要判别传入的特定位置的索引是否有效
    
    具体的，先判断索引 i 是否大于链表长度减1，是则无效，输出-1。
    有效，则根据 链表遍历式 遍历到索引为 i 的节点，然后输出其val。
  - 链表遍历式 上面三种功能都会使用到的辅助函数
    输入索引 index, 通过遍历链表，输出前后两个相邻Node的指针，
    其中，前一个Node的索引为 index - 1, 后一个Node的索引为 index。
    拿到他们俩后，就可以进行任意的增、删、查操作。
    
    注意，这里的 index 最大可以是链表长度 size，
    此时前一个Node其实就是链表最后一个Node，而后一个Node其实是不存在的，返回的指针实际上是null。
    这是因为需要适配 AddTail 的操作：在最后一个Node后面插入一个next为null的Node。
    
    这样的特性，要求查函数里需要先行判断传入的索引是否有效，有效才能调用该遍历式，
    不然会尝试使用一个null的指针去输出其val。

代码：

class MyLinkedList
{
    struct Node
    {
        int val{0};
        Node *next{nullptr};
        Node() = default;
        Node(int val_, Node *next_) : val(val_), next(next_) {}
    };

public:
    Node *vhead{nullptr};
    int size{0};

    MyLinkedList()
    {
        vhead = new Node(0, nullptr);
    }

    void iter_linked_list(Node *&father, Node *&kid, int index)
    {
        if (index <= size)
        {
            father = vhead;
            kid = father->next;
            while (index--)
            {
                father = kid;
                kid = kid->next;
            }
        }
    }

    int get(int index)
    {
        if (index > size - 1)
        {
            return -1;
        }
        Node *_ = vhead, *kid = vhead->next;
        iter_linked_list(_, kid, index);
        return kid->val;
    }

    void addAtIndex(int index, int val)
    {
        if (index < size + 1)
        {
            Node *father = vhead, *kid = vhead->next;
            iter_linked_list(father, kid, index);
            Node *new_node = new Node(val, kid);
            father->next = new_node;
            size++;
        }
    }

    void addAtHead(int val)
    {
        addAtIndex(0, val);
    }

    void addAtTail(int val)
    {
        addAtIndex(size, val);
    }

    void deleteAtIndex(int index)
    {
        if (index < size)
        {
            Node *father = vhead, *kid = vhead->next;
            iter_linked_list(father, kid, index);
            auto temp = kid->next;
            delete kid;
            kid = nullptr;
            father->next = temp;
            size--;
        }
    }
};

206. 反转链表

题目链接：click here
文章讲解：click here
题目描述：给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
思路：比较朴素的一道题，需要细致的把控 next 指针的绑定顺序以及单次遍历内部的操作。
- 比较简单的思路是，强行遍历链表，使用push_front将各个Node的指针记录到deque容器中，
  再遍历该容器，实现next反转。需要额外处理结果链表中的最后一个Node，让他的next指向nullptr。
  
  但这显然是不够的
- 更优雅的做法是一趟遍历完成链表的原地反转：
  首先处理特殊情况，原链表Node个数少于2，则可以直接输出head。
  
  其余情况：
  记录两个相邻的Node，分别为 last，cur。初始化时 last = nullptr，kid = head。
  开始循环，每轮都将 cur 的 next 指针都指向 last，随后右移 last 和 cur 指针，直到遍历到链表尾部。
  循环终止条件：很显然，只要 cur 是valid Node，即内部有数据，就需要将其 next 指针指向 last，所以终止条件是 cur = nullptr，此时 last 是原链表中的最后一个 valid Node，将作为结果链表的 head 被输出。
  
  为了循环能够顺利执行，需要细致处理：每轮都将 cur 的 next 指针都指向 last，随后右移 last 和 cur 指针
  
  先记录原始 cur 的 next 指针为 kid，以便后续 cur 能右移到 kid上，
  然后将 cur 的 next 指针赋值为 last，完成单个节点的反指。
  然后先将 last 移动到 cur，再将 cur 移动到 kid 上，进入下一轮循环。
细节：
核心就是上面三句话，遵循了某种“先记录，后修改”的原则，
比如为了能移动 cur 到下一个位置，需要先记录它原本的 next 为 kid，后修改它的 next 到 last；
为了正确移动 last，需要在 cur 移动到 kid 前，趁着 cur 还记录这 last 的目的地，修改 last 为 cur；
最后再修改 cur 到 kid。

另外就是 last 初始化为 nullptr，是为了使得结果链表的末尾节点的 next 是 nullptr。

代码：

class Solution
{
public:
    ListNode *reverseList(ListNode *head)
    {
        if (!head || !(head->next))
        {
            return head;
        }
        ListNode *cur = head;
        ListNode *last = nullptr;
        while (cur)
        {
            auto kid = cur->next;
            cur->next = last;
            last = cur;
            cur = kid;
        }
        return last;
    }
};

讲解中的双指针法：
和我的思路、代码实现都几乎是一致的。双指针法就适合干这种操作。
讲解中的递归法：
其实where就是可以改造成递归的，所以可见讲解中递归的最终退出条件和循环的退出条件是一致的，cur = nullptr。
当没有达到退出条件时，每次调用函数都将当前拿到的 last 和 cur 执行反指操作，然后继续调用函数，调用的过程就完成了双指针法中关于 cur 和 last 的重新赋值，他俩都整体前进一格。
讲解中的递归法2：
牛儿鼻子，震撼的是，我的思路里，快速退出的两种条件[head为null 或 head->next为null]，被这里用于做迭代收敛条件了。
每次迭代，都是假设调用这个函数能让第二个节点开始的剩余部分完成反转，那么调用函数后，只要让第二个节点的next指向当前第一个节点，再让当前第一个节点指向null，就完成了对整个链表的反转。

具体示意如下：

第1次递归：1->2->3->4->5，将子链2->3->4->5压入函数内
第2次递归：2->3->4->5，将子链3->4->5压入函数内
第3次递归：3->4->5，将子链4->5压入函数内
第4次递归：4->5，将子链5压入函数内（第5次递归函数调用）

此时由于 5->next 是 null，子链5无需反转，函数调用返回表头5，该函数剩余部分将得到：5->4->null

第3次递归：3->4 ，子链 5->4->null，子链完成反转，该函数剩余部分将得到：5->4->3->null
第2次递归：2->3 ，子链 5->4->3->null，子链完成反转，该函数剩余部分将得到：5->4->3->2->null
第1次递归：1->2 ，子链 5->4->3->2->null，子链完成反转，该函数剩余部分将得到：5->4->3->2->1->null

最终返回结果链表的头，即第5次递归函数调用返回的表头5。
细节：
算法的设计就是通过拟定函数的功能，并认为只要调用了该函数就能得到所拟定的结果。
然后，通过不断人为缩小喂入函数内的子链的范围，逐步收敛到子链无需反转情况，结束子链的细分，
然后将反转后的子链的末尾元素反转指向当前函数内链表的头，完成当前这一细分任务[也就是对上一层函数调用该函数时的传入的子链的反转]

如此递递递递，再归归归归的方法，不断地完成小任务，最终聚合起来完成大任务，颇有大事化小，小事化了的思想，亦有分而治之的影子。

然而，递归方法由于栈的调用，需要额外的空间来存储函数指针，似乎时空复杂度和我一开始那种比较暴力的想法是一样的。
进一步的，既然时空复杂度没有得到优化，实战中还是不要写这样的递归函数，边界退出条件弄错了很麻烦，代码的可读性也不如暴力方法。

今日收获

个人博客更新。若Blog有误或是有其他想交流的，左侧有联系方式。
复习：
移除链表元素：****虚拟头节点的应用，避免对头节点的特殊处理；遍历链表的同时删除其中满足特定条件的元素。
设计链表：****巩固增删改查的基础，通过提取公用的遍历链表到指定位置功能为API，简化代码的长度。
反转链表：双指针法实战意义更高，需要细致把控双指针的移动、反转等细节操作。
耗时：4h

Junyuan Lu(陆俊元)

代码随想录算法训练营第三天 | 203. 移除链表元素、707. 设计链表、206. 反转链表

203. 移除链表元素

707. 设计链表

206. 反转链表

今日收获