快慢指针-牛客题霸模板速刷（BM6、BM7、BM8）

标签：结点 slow ListNode 速刷 fast next BM6 BM7 指针

快慢指针是指在链表或其他遍历对象中，通过两个相同方向的指针，即快指针和慢指针，以不同的速度遍历，从而实现寻找某个结点的目的。

BM6-判断链表中是否有环

题解：想象在环形跑道上两个运动员从同一起点出发以不同的速度向前奔跑，则到某一时刻两人一定会到达同一点。快慢指针同理，使快指针每次前移两个结点，慢指针每次前移一个结点，若链表中存在环，则之后快慢指针一定会指向同一结点。

class Solution {
public:
    bool hasCycle(ListNode *head) {
        if(head == NULL)
            return false;
        ListNode* fast = head;
        ListNode* slow = head;
        while(fast != NULL && fast->next != NULL){
            fast = fast->next->next;
            slow = slow->next;
            if(fast == slow)
                return true;
        }
        return false;
    }
};

 

BM7-链表中环的入口结点

题解：使快慢指针以不同的速度前移，找到相遇的结点。而后让快指针指向头结点，让两个指针以相同的速度前移，两指针相遇的结点即为链表中环的入口结点。

class Solution {
  public:
    ListNode* hasCycle(ListNode* head) { 
        if (head == NULL)
            return NULL;
        ListNode* fast = head;
        ListNode* slow = head;
        while (fast != NULL && fast->next != NULL) { 
            fast = fast->next->next;
            slow = slow->next;
            if (fast == slow)
                return slow;
        }
        return NULL;
    }
    ListNode* EntryNodeOfLoop(ListNode* pHead) {
        ListNode* slow = hasCycle(pHead);
        if (slow == NULL)
            return NULL;
        ListNode* fast = pHead;
        while (fast != slow) {
            fast = fast->next;
            slow = slow->next;
        }
        return slow;
    }
};

 

BM8-链表中倒数最后k个结点

题解：开始时快慢指针同时指向头结点，先让快指针向前移动k个结点，再让慢指针和快指针以同样的速度前移，当快指针到达链表尾端时，慢指针前移了n-k个结点，即指向了链表中倒数第k个结点

class Solution {
public:
    ListNode* FindKthToTail(ListNode* pHead, int k) {
        ListNode* fast = pHead;
        ListNode* slow = pHead;
        for(int i = 0; i < k; i++){
            if(fast != NULL)
                fast = fast->next;
            else
                return slow = NULL;
        }
        while(fast != NULL){
            fast = fast->next;
            slow = slow->next;
        }
        return slow;
    }
};

 

标签：结点,slow,ListNode,速刷,fast,next,BM6,BM7,指针
From： https://www.cnblogs.com/LiXinjuan/p/17072319.html