leetcode 142. Linked List Cycle II 快慢指针寻找环 + 快慢指针寻找环入口

怼烎@ 2022-06-08 06:06 181阅读 0赞

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Note: Do not modify the linked list.

Follow up:  
Can you solve it without using extra space?

和上一道题不一样的是[leetcode 141. Linked List Cycle 链表循环的判定 + 双指针][leetcode 141. Linked List Cycle _ _]，这道题还要求求出环的入口结点。

可以使用双指针来判断是否存在环。两个指针相遇的时候，我们设相遇点为c，此时fp和sp都指向了c，接下来令fp继续指向c结点，sp指向链表头结点head，此时最大的不同是fp的步数变成为每次走一步，令fp和sp同时走，每次一步，那么它们再次相遇的时候即为环的入口结点。

具体为什么呢？我也没搞懂，先这么办吧！

代码如下：

/*class ListNode 
    {
        int val;
        ListNode next;
        ListNode(int x) {
            val = x;
            next = null; }
    }*/
    
    public class Solution 
    {
        /*
         *http://blog.csdn.net/derrantcm/article/details/47774563
         * 
         * 这个解释很形象
         * 
         * 题目要求是判断链表是否有环，leetcode上链表的题都是没有头结点的，这点大家要记住。
         * 而且若链表有环，也是最后一个节点形成的环。
         * 大家考虑这样一个问题，链表的环相当于一个圆形操场。假设有两个人在圆形操场上无限循环的跑，
         * 那么速度快的一定能追得上速度慢的。同理，若要判断一个链表是否有环，可设计快慢指针，
         * 当快慢指针都进入环的时候，若最终两个指针相遇，必可说明链表存在环。下面就要考虑快慢指针的步长，
         * 从跑操场的情况来看，不管慢的有多慢，快得有多快，最终肯定能相遇。同理，链表中，
         * 也可随意指定快慢指针的步长，无非就是跑的圈数多少的问题。 
         * 
         * http://blog.csdn.net/willduan1/article/details/50938210
         * 如果链表中存在环，那么fp和sp一定会相遇，当两个指针相遇的时候，我们设相遇点为c，
         * 此时fp和sp都指向了c，接下来令fp继续指向c结点，sp指向链表头结点head，此时最大的不同是fp
         * 的步数变成为每次走一步，令fp和sp同时走，每次一步，那么它们再次相遇的时候即为环的入口结点。
         * 接下来我们也许想知道为什么fp和sp指向上面所说的结点之后同时以步数为一走再次相遇的时候一定会
         * 指向环的入口结点.
         * */
        public ListNode detectCycle(ListNode head) 
        {
            if(head==null || head.next==null)
                return null;
    
            ListNode fast=head,slow=head;
            boolean find=false;
            while(fast!=null && slow!=null && fast.next!=null)
            {
                slow=slow.next;
                fast=fast.next.next;
                if(fast==slow)
                {
                    find=true;
                    break;
                }
            }
            if(find)
            {
                //找到循环的开始结点，这个时候快慢指针的速度是一致的，这个时候再一次相遇的时候就是循环的入口
                 slow = head;
                 while (slow != fast) 
                 {
                        slow = slow.next;
                        fast = fast.next;                                
                 }
                 return slow;
            }else 
                return null;
        }
    }

下面是C++的做法，和上一道题一样，就是使用双指针来解决问题

代码如下：

#include <iostream>
    #include <vector>
    #include <algorithm>
    #include <string>
    #include <map>
    #include <set>
    #include <climits>
    
    using namespace std;
    
    /*
    struct ListNode 
    {
         int val;
         ListNode *next;
         ListNode(int x) : val(x), next(NULL) {}
    };
    */
    
    class Solution
    {
    public:
        ListNode* detectCycle(ListNode *head)
        {
            if (head == NULL || head->next == NULL)
                return NULL;
    
            ListNode* fast = head;
            ListNode* slow = head;
            bool find = false;
            while (fast != NULL && slow != NULL && fast->next != NULL)
            {
                slow = slow->next;
                fast = fast->next->next;
                if (fast == slow)
                {
                    find = true;
                    break;
                }
            }
            if (find)
            {
                slow = head;
                while (slow != fast)
                {
                    slow = slow->next;
                    fast = fast->next;
                }
                return slow;
            }
            else
                return NULL;
        }
    };

[leetcode 141. Linked List Cycle _ _]: http://blog.csdn.net/jackzhang_123/article/details/78003026