Leetcode: 【每日一题】- 2020-01-14 - 142. 环形链表 II

[azl397985856]

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。

说明：不允许修改给定的链表。

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：tail connects to node index 1
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

输入：head = [1,2], pos = 0
输出：tail connects to node index 0
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

输入：head = [1], pos = -1
输出：no cycle
解释：链表中没有环。

进阶：
你是否可以不用额外空间解决此题？

[unclegem]

假设从链表开始的位置到环入口的距离为p，慢指针在环内走了的距离为c，假设慢指针一共走了n步，快指针一共做了2n步。
那么，有p+c=n
显然，从p+c这一点开始，慢指针再走n步，必然还会回到这个点。为啥？【因为经过了2n步，快指针到达了这一点，所以慢指针如果再走n步，也会到达这一点】
如果让快指针从链表头开始走n步，也会到达p+c这个位置，二者相遇的第一个地方，肯定是环入口。

    public ListNode detectCycle(ListNode head) {

        ListNode slow = head, fast = head;

        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
            if(fast == slow){

                ListNode slow2 = head;
                while(slow2 != slow){
                    slow = slow.next;
                    slow2 = slow2.next;
                }

                return slow;         
            }           
        }

        return null; 
    }

    def detectCycle(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if fast == slow:
                fast = head
                while fast != slow:
                    fast = fast.next
                    slow = slow.next
                return slow

[azl397985856]

Two Pointer(Python Code)

• x means the first meeting point

• assume L is the length between the start point and the entry point of the loop.

• and C is the length between the entry point and x

• and D is the remaining part of the circle.

2(L + C) is the distance which fast traveled, and so does L + 2C + D

So we setup two pointers which steps range from one to two. when the two pointers meets, slow point starts from start point again, fast point continue. Absolutely, we can meet at the entry point, because L = D

That's all!

#
# @lc app=leetcode.cn id=142 lang=python3
#
# [142] 环形链表 II
#

# @lc code=start
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None


class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        slow = fast = head
        x = None

        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
            if fast == slow:
                x = fast
                break
        if not x:
            return None
        slow = head
        while slow != x:
            slow = slow.next
            x = x.next
        return slow

[stale[bot]]

This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions.