快慢指针

本文持续更新中

概述

快慢指针是解决链表中一些问题的常用手段。通常有三种手段

1. 快指针与慢指针之间存在恒定的距离差，快指针一定领先慢指针N个节点。通常解决链表中倒数第N个节点此类问题

2. 快指针与慢指针之间存在恒定的速率差，快指针一次移动两个结点，慢指针一次移动一个结点，根据这个速率差解决问题。通常解决找链表中点，循环链表等问题。

3. 双指针同步运动，但是构造某种等量关系让本来不相等的距离相等。

注意，本文提到的几道题可能不只有一种解法，本文只选取快慢指针相关的解法，其它解法不再赘述。

链表的倒数第N个节点

例题：19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode）

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

题解：

快慢指针，快指针领先慢指针n个结点，快指针移动到末尾时，慢指针移动到要删除的结点。考虑到要删除该结点，找到该结点的前驱结点比较合适，故设置了一个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* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummy = new ListNode(0, head);
        ListNode* slow = dummy;
        ListNode* fast = head;
        for(int i = 0;i<n;i++){
            fast = fast->next;
        }
        while(fast != nullptr){
            fast = fast->next;
            slow = slow->next;
        }
        slow->next = slow->next->next;
        ListNode* ans = dummy->next;
        delete dummy;
        return ans;
    }
};

环形链表相关

环形链表相关问题使用快慢指针，二者以固定速率差运动，最后一定会在环内某一点相遇，可以借以此判断是否存在环形链表，甚至进一步可判断入环点位置。

例题：142. 环形链表 II - 力扣（LeetCode）

给定一个链表的头节点  head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

题解：

可以直接看我在LeetCode每日一题系列下面写的内容：LeetCode每日一题：142. 环形链表 II - fan4w

从图上可知从相遇点到入环点的距离加上n−1圈的环长，恰好等于从链表头部到入环点的距离。

也就是说，慢指针向前运动到入环点的时候，指针head距离入环点刚好是环长的整数倍，head运行到入环点时，慢指针一定刚好绕完整数圈环，二者相遇。以下是官方代码：

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode *slow = head, *fast = head;
        while (fast != nullptr) {
            slow = slow->next;
            if (fast->next == nullptr) {
                return nullptr;
            }
            fast = fast->next->next;
            if (fast == slow) {
                ListNode *ptr = head;
                while (ptr != slow) {
                    ptr = ptr->next;
                    slow = slow->next;
                }
                return ptr;
            }
        }
        return nullptr;
    }
};

作者：力扣官方题解
链接：https://leetcode.cn/problems/linked-list-cycle-ii/solutions/441131/huan-xing-lian-biao-ii-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

链表相交

例题：160. 相交链表 - 力扣（LeetCode）

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

图示两个链表在节点 c1 开始相交：

题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

题解：

构造指针pA和pB，同时向前运动，运动到链表末尾时，回退到另一个链表的起始点

pA = (pA == nullptr) ? headB : pA->next;
pB = (pB == nullptr) ? headA : pB->next;

• 若相交，链表A的长度是a+c，链表B的长度是b+c，a+c+b=b+c+a，故一定在相交点相遇；

• 若不相交，链表A长度是a，链表B长度是b，运动a+b时在nullptr相遇

以下是完整代码：

/**
 * 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 nullptr;
        }
        ListNode* pA = headA;
        ListNode* pB = headB;
        while(pA != pB){
            pA = (pA == nullptr) ? headB : pA->next;
            pB = (pB == nullptr) ? headA : pB->next;
        }
        return pA;
    }
};