Leetcode: Linked List Cycle II

àì夳堔傛蜴生んèń 2022-08-07 11:57 10阅读 0赞

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

思路分析：  
和《[Leetcode: Linked List Cycle][Leetcode_ Linked List Cycle] 》一样还是双指针的方法。  
  
![循环链表][20150405115649335]  
  
一个循环链表如图  
slow指针走了S=X+Y  
fast指针走了F=X+Y+Z+Y  
两个指针相遇。  
且有：2S=F，则有X=Z。  
所以，从head到环开始的路程 ＝ 从相遇到环开始的路程。  
所以，当slow和fast相遇了，我们拿slow从头开始走，fast从相遇的地方开始走，两个都走一步，那么再次相遇必定是环的开始节点。

C++参考代码：

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */
    class Solution
    {
    public:
        ListNode *detectCycle(ListNode *head)
        {
            if (!head) return nullptr;
            ListNode *slow = head;
            ListNode *fast = head;
            bool hasCycle = false;
            while (fast && fast->next)
            {
                slow = slow->next;
                fast = fast->next->next;
                if (slow == fast)
                {
                    hasCycle = true;
                    break;
                }
            }
            if (hasCycle)
            {
                slow = head;
                while (slow != fast)
                {
                    slow = slow->next;
                    fast = fast->next;
                }
                return slow;
            }
            else return nullptr;
        }
    };

C\#参考代码：

/** * Definition for singly-linked list. * public class ListNode { * public int val; * public ListNode next; * public ListNode(int x) { * val = x; * next = null; * } * } */
    public class Solution { 
        public ListNode DetectCycle(ListNode head)
        {
            if (head == null) return null;
            ListNode slow = head;
            ListNode fast = head;
            bool hasCycle = false;
            while (fast != null && fast.next != null)
            {
                slow = slow.next;
                fast = fast.next.next;
                if (slow == fast)
                {
                    hasCycle = true;
                    break;
                }
            }
            if (hasCycle)
            {
                slow = head;
                while (slow != fast)
                {
                    slow = slow.next;
                    fast = fast.next;
                }
                return slow;
            }
            else return null;
        }
    }

[Leetcode_ Linked List Cycle]: http://blog.csdn.net/theonegis/article/details/44886333
[20150405115649335]: /images/20220805/388aaa84c3ab4dddb586fb8a27f1f047.png