首页 > 代码库 > [leetcode]Linked List Cycle II @ Python

[leetcode]Linked List Cycle II @ Python

原题地址:http://oj.leetcode.com/problems/linked-list-cycle-ii/

题意:如果链表中存在环路,找到环路的起点节点。

解题思路:这道题有点意思。首先使用快慢指针技巧,如果fast指针和slow指针相遇,则说明链表存在环路。具体技巧参见上一篇http://www.cnblogs.com/zuoyuan/p/3701639.html

在fast指针和slow指针相遇后,fast指针不动,slow指针回到head,然后slow指针和fast指针同时向前走,只不过这一次两个指针都是一步一步向前走。两个指针相遇的节点就是环路的起点。

示意图:

原理说明:图中,head到环路起点的距离为K,起点到fast和slow的相遇点的距离为M,环路周长为L。假设,在fast和slow相遇时,fast走过了Lfast,slow走过了Lslow。根据题意:

     Lslow=K+M;Lfast=K+M+n*L(n为正整数);Lfast=2*Lslow

       可以推出:Lslow=n*L;K=n*L-M

     则当slow重新回到head,而fast还在相遇点,slow和fast都向前走,且每次走一个节点。

       则slow从head走到起点走了K,而fast从相遇点出发也走了K,而fast向前走了距离K后到了哪里呢?由于K=(n-1)*L+(L-M),所以fast转了n-1圈,再走L-M,也到了起点。这样起点就找到了。

代码:

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

class Solution:
    # @param head, a ListNode
    # @return a list node
    def detectCycle(self, head):
        if head == None or head.next == None:
            return None
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if fast == slow:
                break
        if slow == fast:
            slow = head
            while slow != fast:
                slow = slow.next
                fast = fast.next
            return slow
        return None