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

203.移除链表元素

题目链接：203.移除链表元素

很基本的链表操作，需要注意的是我们可以考虑在头结点前再增加一个虚拟节点dummyHead：它不实际存储数据，主要作用是用来统一头结点和其他节点的增删操作。

ListNode* dummyHead = new ListNode(0);
// 让虚拟头节点指向链表头节点
dummyHead->next = head;

完整代码如下：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode* dummyHead = new ListNode();
        dummyHead->next = head;
        ListNode* cur = dummyHead;
        while (cur->next != NULL) {
            if (cur->next->val == val) {
                ListNode* tmp = cur->next;
                cur->next = cur->next->next;
                // 删除节点做好内存释放
                delete tmp;
            }
            else {
                cur = cur->next;
            }
        }
        return dummyHead->next;
    }
};

注意最后返回的链表头节点是虚拟头节点的下位节点dummyHead->next！！！因为链表本身的头节点可能在遍历过程中被删除。

707.设计链表

题目链接：707.设计链表

题干设计一系列链表相关的函数，不涉及算法，主要是对不同函数的输入参数的异常处理进行全面考虑：

• get(index)：如果索引无效（小于0或者大于等于链表长度），返回-1
• addAiIndex(index, val)：这里对异常输入进行一些包容处理：
  • index等于链表长度，插入到链表末尾
  • index小于0（也包括等于0的情况），插入到链表头部
  • index大于链表长度，则不会插入节点
• deleteAtIndex：index小于0或者等于链表长度，则不做处理

由于该类定义中增加了链表长度的计数，所以每次进行链表节点增删的时候，都记得对计数长度len进行更改。另外设计的链表中新增了虚拟头结点dummyHead来统一对头节点和其他节点的增删操作。

代码如下：

class MyLinkedList {
public:
    // 先定义头结点数据结构
    struct ListNode {
        int val;
        ListNode* next;
        ListNode() : val(0), next(nullptr) {}
        ListNode(int x) : val(x), next(nullptr) {}
    };

    MyLinkedList() {
        dummyHead = new ListNode();
        len = 0;
    }
    
    int get(int index) {
        if (index < 0 || index >= len)
            return -1;
        ListNode* cur = dummyHead;
        while (index--) {
            cur = cur->next;
        }
        return cur->next->val;
    }
    
    void addAtHead(int val) {
        ListNode* node = new ListNode(val);
        node->next = dummyHead->next;
        dummyHead->next = node;
        len++;
    }
    
    void addAtTail(int val) {
        ListNode* node = new ListNode(val);
        ListNode* cur = dummyHead;
        while (cur->next != nullptr)
            cur = cur->next;
        cur->next = node;
        len++;
    }
    
    void addAtIndex(int index, int val) {
        // 先进行异常处理步骤
        if (index > len) 
            return;
        else if (index == len) {
            addAtTail(val);
        }
        else if (index <= 0) {
            addAtHead(val);
        } 
        else {
            ListNode* node = new ListNode(val);
            ListNode* cur = dummyHead;
            while (index--) {
                cur = cur->next;
            }
            node->next = cur->next;
            cur->next = node;
            len++;
        }
    }
    
    void deleteAtIndex(int index) {
        // 先进行异常处理
        if (index < 0 || index >= len)
            return;
        ListNode* cur = dummyHead;
        while (index--) {
            cur = cur->next;
        }
        ListNode* tmp  = cur->next;
        cur->next = cur->next->next;
        delete tmp;
        len--;
    }

private:
    // 建立头结点，统一增删操作
    ListNode* dummyHead;
    int len;
};

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList* obj = new MyLinkedList();
 * int param_1 = obj->get(index);
 * obj->addAtHead(val);
 * obj->addAtTail(val);
 * obj->addAtIndex(index,val);
 * obj->deleteAtIndex(index);
 */

206.反转链表

题目链接：206. 反转链表

反转链表时当节点的next修改为其父节点后，这会打断链表的遍历路径，如何处理是本题的关键？

①双指针法

双指针法采用了一前一后两个指针，用来重新建立next连接，并且在建立前会将遍历指针的后续节点先临时保存在temp中，建立连接后再重新更新前后两个指针节点。简单来讲，链表不是通过遍历而是用值交换（Swap）的方式进行赋值的。

代码如下：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        // 指针不在链表上遍历，而是依赖于临时变量进行传递
        ListNode* pre = nullptr;
        ListNode* cur = head;
        while (cur != nullptr) {
            ListNode* tmp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = tmp;
        }
        // 最后翻转链表的头指针在pre
        return pre;
    }
};

注意反转终止的条件是cur指针遍历到了链表的空指针上，此时pre指针恰好是反转链表的头指针。

②递归法

本质的思想跟双指针法类型，仅仅是将循环的调用用函数的形式进行替换。

• 首先是前后指针的更新用函数的形参代替赋值语句

  建立的递归函数reverse(ListNode* pre, ListNode* cur)中两个形参分别代表了前后指针：更新的前指针是老的cur指针，更新的后指针是临时保存的temp指针。

• 循环终止条件替换成递归函数的终止条件

  cur == nullptr的情况实际上就是链表遍历到尾部的空指针。

代码如下：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        return reverse(nullptr, head);
    }

    // 构造递归函数
    ListNode* reverse(ListNode* pre, ListNode* cur) {
        // 先设置终止条件
        if (cur == nullptr)
            return pre;
        ListNode* temp = cur->next;
        cur->next = pre;
        // 此时再将temp作为新的cur节点，cur作为新的pre节点输入函数
        return reverse(cur, temp);
    }
};