fan4w
fan4w
发布于 2023-07-31 / 66 阅读 / 0 评论 / 0 点赞

快慢指针

本文持续更新中

概述

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

  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

841FA64D20BB6C1C4FF011E515E7C839.png从图上可知从相遇点到入环点的距离加上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)

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

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

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

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

题解:

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

pA = (pA == nullptr) ? headB : pA->next;
pB = (pB == nullptr) ? headA : pB->next;
  • 若相交,链表A的长度是a+c,链表B的长度是b+ca+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;
    }
};


评论