剑指55-链表中环的入口结点

Posted on | In |

题目描述

给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。

  • 从链头到链尾遍历链表并对访问一个节点做记录，每访问一个节点，还要检查其否是被访问过。第一个重复访问的节点，必然是环的入口节点。
  • 需要O(n)的空间复杂度。
1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def EntryNodeOfLoop(self, pHead):
        if not pHead: 
            return None
        idSet = set()
        while pHead:
            if id(pHead) in idSet:
                return pHead
            else:
                idSet.add(id(pHead))
                pHead = pHead.next
        return None
  • 一快一慢两个指针遍历链表必然会相遇，相遇节点必在环上。
  • 由环上一节点开始，循环一周，可得环上节点数。
  • 两个指向链表头的指针，其中一个先移动步数位环上节点数，然后二者以相同的速度移动，首次相遇必在入口节点。
    • 设环上节点数n，一共有节点数L，则不在环上的节点有L-n个。设相遇时第二个节点移动了x步，则第一个指针一共移动了n+x步。当x=L-n时，有第一个节点刚好遍历完所有节点，当前指向环的入口节点；而第二个节点也指向同样的节点，也就是说二者会相遇。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
    def EntryNodeOfLoop(self, pHead):
        if pHead is None:
            return None
        # 通过两指针相遇找环上节点
        p1, p2 = pHead, pHead.next
        while p1 != p2:
            if p1.next is None or p2.next is None or p2.next.next is None:
                return None
            p1 = p1.next
            p2 = p2.next.next
        # 获得环上节点数   
        p2 = p2.next
        nloop = 1
        while p1 != p2:
            nloop += 1
            p2 = p2.next
        # 找到入口节点
        p1, p2 = pHead, pHead
        for i in range(nloop):
            p2 = p2.next
        while p1 != p2:
            p1 = p1.next
            p2 = p2.next
        return p1