142. 环形链表 II

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

class Solution(object):
    def detectCycle(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if head is None or head.next is None:
            return None
        slow = fast = head
        while slow.next and slow.next.next:
            slow = slow.next         #慢指针
            fast = fast.next.next  #快指针
            if fast == slow:
                index = head
                while fast != index:
                    index = index.next
                    fast = fast.next
                return index
        return None

快慢指针方法寻找环。慢指针一次移动一位，快的一次移动两位，肯定能在环里相遇。

关键就是什么条件是环的起始点：
可参考https://blog.****.net/l294265421/article/details/50478818
142. 环形链表 II
1.首先要证明的是，两指针相遇时，慢指针还没有走完整个链表的环。因为快指针是慢的两倍，慢指针走一圈快指针要走两圈

我们以最极端的情况来说，假设快指针这时就在慢指针的前面一个节点，这时，快指针追上慢指针需要走最长的距离。因为快指针的速度是慢指针的两倍，所以慢指针走一圈，快指针走两圈，当慢指针第一次在环上走完一圈回到Join点时，快指针刚好走完两圈

2.快慢指针相遇后，慢指针再往前移A个节点就刚好到达Join点也就是A=y
假设第一次相遇点为Pos，环起点为Join，头结点到环起点的长度为A，环起点到第一次相遇点的长度为x，第一次相遇点到环起点的长度为y，环长为R
1.第一次相遇时，slow走的长度 S1 = A + x
2.第一次相遇时，fast多走一圈的长度 S2 = A + R + x 而且快指针是慢的两倍 S2=2S1
3.由1和2得 A + x = R; A = R -x;
4.证明：y=R-x 也就是 A=R-x

142. 环形链表 II

相关推荐