有环链表

判断链表是否有环是一个很经典的问题,也可以引申出其他的问题,比如找到链表入环的节点.
通常的解决办法是通过两个指针,一个fast,一个slow,其中fast每次走两个节点,slow只走一个节点.如果链表有环的话,那么他们最终一定会相遇.如果fast提前走到了链表的结尾,那么说明这个链表无环.

判断链表是否有环

Linked List Cycle:

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

class Solution(object):
    def hasCycle(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        if not head:
            return False
        
        slow = fast = head
        
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                return True
        return False

寻找环的入口

Linked List Cycle II

假设链表头距离环的入口距离为m,fast与slow节点在距离节点顺时针距离为n的地方相遇.假设环的剩余部门长度是l,如上图所示.
那么:

fast经过的距离: sf = m + k(l + n) + n = m + kl + (k+1)n
slow经过的距离: sl = m + n

k为fast在环中走的圈数(k >= 1, fast至少会多跑一圈),即fast在完整的走了k圈之后,再走了距离为n,才与slow相遇

而sf是sl的两倍:

m + kl + (k+1)n = 2(m + n)

可以得到:

kl + (k-1)n = m

即:

l + (k-1)(l+n) = m

l+n是一个环的距离,也就是说m的长度等于l再加上又跑了k-1圈的距离.特别地,当k=1时, m = l.

因此只需要将fast节点重新回到链表头,那么他们就会在链表环入口的地方重新相遇.

class Solution(object):
    def detectCycle(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        f = s = head
        while f and f.next:
            f = f.next.next
            s = s.next
            if f == s:
                break
        if not f or not f.next:
            return
        f = head
        while f:
            if f == s:
                return f
            f = f.next
            s = s.next

标签：shangdixinxi   上地信息