代码随想录：链表

移出链表元素

lc203.移除链表元素

• 题目lc203
• 思路：注意这里的头节点也有val，所以分两种情况，头节点和非头结点
• 代码如下：

/**
 * 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) {
        // 如果为空，直接返回
        if(head == nullptr){
            return head;
        }
        ListNode* temp;
        // 如果头节点是val
        while(head && head->val == val){
            temp = head;
            head = head->next;
            delete(temp);
        }
        // 如果非头节点是val
        temp = head;
        ListNode* before_temp = head;  // 指向temp的前一个节点
        while(before_temp && before_temp->next != nullptr){
            if(temp->val == val){
                before_temp->next = temp->next;
                delete(temp);
                temp = before_temp;
            }
            before_temp = temp;
            temp = temp->next;
        }
        return head;
    }
};

• 看了官方题解，思路：先加入一个头节点，这样每个节点的操作都一样
• 代码如下：

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode* new_head = new ListNode(0, head);
        ListNode* temp = new_head;
        while(temp->next){
            if(temp->next->val == val){
                ListNode* delete_node = temp->next;
                temp->next = delete_node->next;
                delete(delete_node);
            } else{
                temp = temp->next;
            }
        }
        return new_head->next;
    }
};

lc206 反转链表

• 题目lc206
• 思路：三个指针，一个指向前一个节点，一个指向当前节点，一个指向后一个节点
• 代码如下：

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* pre = nullptr, *cur = head;
        ListNode* temp = nullptr;
        while(cur != nullptr){
            temp = cur->next;
            cur->next = pre;
            // 向后移动
            pre = cur;
            cur = temp;
        }
        return pre;
    }
};

lc24. 两两交换链表中的节点

• 题目lc24
• 同上，用三个指针交换，加入头节点，详细思考过程见代码
• 代码如下：

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        // 先分析中间节点如何两两交换：改变3个指针，如样例234(交换34)
        // 指针变化为：3->next(4), 4->3, 2->4
        // 考虑第一个节点，不需要类似2->4的指针变化，为了每个节点都用一样的操作，加一个dummy_head
        if(head == nullptr){
            return nullptr;
        }
        ListNode* dummy_head = new ListNode(-1, head);
        ListNode* pre = dummy_head, * cur = head, *next = head->next;
        while(cur && next){
            // 三个指针变化
            cur->next = next->next;
            next->next = cur;
            pre->next = next;
            // 向后移动
            pre = cur;
            cur = cur->next;
            if(cur != nullptr){
                next = cur->next;
            }
        }
        return dummy_head->next;
    }
};

lc19. 删除链表的倒数第 N 个结点

• 题目lc19
• 思路和代码如下：

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        // 为了保证头节点操作相同，加入dummy_head
        // 设链表长度为x + 1, 删除倒数第n个节点，即正数第(x + 1 - n + 1)个节点
        // 快慢指针：快指针先走(n + 1)个节点，然后快慢指针同时移动
        // 当快指针 == nullptr，慢指针就移动了(x - n + 1)个节点，到达删除节点的前一个节点
        // 最后进行删除操作
        ListNode* dummy_head = new ListNode(-1, head);
        ListNode* fast = dummy_head->next, *slow = dummy_head;
        for(int i = 0; i < n; i++){
            fast = fast->next;
        }
        while(fast){
            fast = fast->next;
            slow = slow->next;
        }
        slow->next = slow->next->next;  // 忽略了delete操作
        return dummy_head->next;
    }
};

面试题 02.07. 链表相交

• 题目lc02.07
• 思路和代码如下：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        // 先分别计算两个链表的长度，再让长链表移动使得两个链表长度相同
        // 最后同时移动两个链表，直到相交或结尾
        if(headA == nullptr || headB == nullptr){
            return NULL;
        }
        int lenA = 0, lenB = 0;
        ListNode* temp = headA;
        while(temp != nullptr){
            lenA++;
            temp = temp->next;
        }
        temp = headB;
        while(temp != nullptr){
            lenB++;
            temp = temp->next;
        }
        // 移动长链表
        while(lenA > lenB){
            lenA--;
            headA = headA->next;
        }
        while(lenB > lenA){
            lenB--;
            headB = headB->next;
        }
        // 同时移动两个链表
        while(headA != nullptr && headB != nullptr){
            if(headA == headB){
                return headA;
            }
            headA = headA->next;
            headB = headB->next;
        }
        return NULL;
    }
};

lc142. 环形链表 II

• 题目lc142
• 思路
  • 先通过快慢指针找到相遇点：快指针向前走2步，慢指针每次走一步，如果有环总会相遇，如果fast为空则没有环
  • 再通过双指针找到入口点：这里需要一些简单的数学推导，设head到入口点距离为x，我们用p指针从head走到入口节点；设入口节点到相遇点（用q指针）距离为y，相遇点到入口点距离为z；两条约束式，slow走的距离：x + y，fast距离：x + y + n(y + z)，因为多走n圈；第二条约束式：slow距离 * 2 = fast距离；最后得出x = (n - 1)(y + z) + z，用代码实现就是q指针从fast和slow相遇点出发，走n圈以及z的距离，就会和p指针从head出发在入口节点相遇
• 代码如下：

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        // 判断有没有环
        ListNode* fast = head, *slow = head;
        while(fast != NULL && fast->next != NULL){
            fast = fast->next->next;
            slow = slow->next;
            if(fast == slow){
                // 找到环的第一个节点
                ListNode *p = head, *q = fast;
                while(p != q){
                    p = p->next;
                    q = q->next;
                }
                return p;
            }
        }
        return NULL;
    }
};