快慢指针

142 环形链表 II (opens new window)

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

输入是一个链表，输出是链表的一个节点，如果没有环路，返回一个空指针。

输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。

解析：

​ 通常使用 Floyd 判圈法，解决链表找环路的问题。其基本思路就是使用快慢指针，快指针一次走两步，慢指针一次走一步，如果这两个指针会相遇则说明存在环路。现在再用一个指针从链表头节点开始一次走一步，慢指针从两个指针相遇的点开始继续一次一步往前走，当这两个指针相遇时，就是环路的入口。

​ 根据上述思路，我们给定两个指针，分别命名为 slow 和 fast，起始位置在链表的开头。每次 fast 前进两步，slow 前进一步：

• 如果 fast可以走到尽头，那么说明没有环路；
• 如果 fast 可以无限走下去，那么说明一定有环路，且一定存在一个时刻 slow 和 fast 相遇。

​ 如果存在环路，当 slow 和 fast 第一次相遇时，我们将 fast 重新移动到链表开头，并让 slow 和 fast 每次都前进一步。当 slow 和 fast 第二次相遇时，相遇的节点即为环路的开始点。

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

206 反转链表 (opens new window)

给定单链表的头节点 head ，请反转链表，并返回反转后的链表

输入一个链表，输出一个反转后的链表

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

解析：

​ 反转链表是快慢指针的经典应用场景。

​ 为了便于统一节点处理方式，我们在链表中加入一个虚拟头节点dummy，其 next 指向链表头节点。然后我们给定两个指针 slow 和 fast，初始时分别指向 dummy 和链表头节点。然后我们进行反转操作：

• 首先使用 tmp 保存 fast 的 next 指向的节点
• 反转 fast 的 next 指向，指向前一节点即 slow
• 移动 slow 到当前 fast
• 更新 fast 指向为其原始 next 指向节点，即 tmp 保存的节点

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode *slow = nullptr, *fast = head;
        while(fast){
            // 为了便于理解，我还是新建了 tmp。当然你可以直接使用闲置的 head 记录，节省空间开销
            ListNode* tmp = fast->next;
            fast->next = slow;
            slow = fast;
            fast = tmp;
        } 
        return slow;
    }
};

19 删除链表的倒数第 N 个结点 (opens new window)

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

输入一个链表，输出一个按条件操作之后的链表

输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

解析：

​ 对于本题首先我们来考虑删除链表的第 N 个节点怎么操作。我们可以使用一个指针从头节点开始遍历找到链表的第 N-1 个节点，然后改变其 next 指向为 next->next ，最后删除第 N 个节点即可。

​ 那么我们怎么删除倒数第 N 个节点呢？我们要找到倒数第 N 个节点的前一个节点。假设链表总共有 M 个节点，那么倒数第 N 个节点就是第 M - N 个节点。

​ 所以我们可以使用快慢指针，快指针 fast 先遍历到链表的第 N 个节点，此时慢指针 slow 再出发与 fast 同步移动。当 fast 遍历完链表最后一个节点时，slow 指向的就是倒数第 N 个节点。

​ 为了便于删除操作，我们让 fast 先遍历到第 N+1 个节点，这时当 fast 遍历完时，slow 指向就是倒数第 N+1 个节点，即待删除节点的前一个节点。

​ 值得注意的是，我们定义一个虚拟头节点指向链表的头节点，这样同一的对头节点的删除操作。

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        // 创建虚拟头节点
        ListNode* dummy = new ListNode(0,head);
        ListNode *slow = dummy, *fast = dummy;
        // 让 fast 先遍历到第 N+1 个节点
        int cnt = 0;
        while(cnt < n+1){
            fast = fast->next;
            ++cnt;
        }
        // 慢指针 slow 与 fast 同步移动到第 N+1 个节点
        while(fast){
            fast = fast->next;
            slow = slow->next;
        }
        // 删除第 N 个节点
        ListNode* tmp = slow->next;
        slow->next = slow->next->next;
        delete(tmp);
        return dummy->next;
    }
};