leetcode之Linked List Cycle II

這題在I的基礎上不僅要判斷，更要找出來是哪個節點開始結合。采用的方法是計算出第一次相遇的時候每次挪一步的那個一共走了x步，再算出來環的大小y。那麼x - y就等于從頭開始走的時候，距離結合點的距離等于相遇點的距離的那個點。然後2個點一起走，相遇的那個點就一定是結合點啦。代碼如下：

# 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 not head:
            print '1111'
            return None
        if not head.next:
            return None
        twostep = head.next.next
        distance1 = 0
        left = head
        #distance1是相遇前一共走了多少步，cycle是環的大小。
        while True:
            if head.next == twostep:
                distance1 = distance1 + 1
                cycle = 0
                head1 = head.next
                while True:
                    if head1.next != head.next:
                        cycle = cycle + 1
                        head1 = head1.next
                    else:
                        cycle = cycle + 1
                        for i in range(distance1 - cycle):
                            left = left.next
                        while True:
                            if left == head.next:
                                return left
                            else:
                                left = left.next
                                head = head.next
            else:
                head = head.next
                distance1 = distance1 + 1
                if not twostep:
                    return None
                elif not twostep.next:
                    return None
                else:
                    twostep = twostep.next.next