LeetCode 142. 环形链表 II（中）& 剑指offer 面试题23. 链表中环的入口

2020腾讯暑期实习一面题目，LeetCode 142. 环形链表（易）的升级版，需要输出循环开始位置。

链表、双指针

LeetCode官方题解 题目来源：力扣（LeetCode）

题目

给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。

说明：不允许修改给定的链表。

示例 1：

1
2
输入：head = [3,2,0,-4], pos = 1
输出：tail connects to node index 1

解释：链表中有一个环，其尾部连接到第二个节点。

circularlinkedlist.png

示例 2：

1
2
输入：head = [1,2], pos = 0
输出：tail connects to node index 0

解释：链表中有一个环，其尾部连接到第一个节点。

circularlinkedlist_test2.png

示例 3： 

1
2
输入：head = [1], pos = -1
输出：no cycle
解释：链表中没有环。

进阶：你是否可以不用额外空间解决此题？

测试用例

功能测试（链表中包含或者不包含环；链表中有多个或者只有一个节点）。 特殊输入测试（链表头节点为nullptr指针）。

直觉

基于Hash Map

基于hash表检查第一个之前就被访问过的节点，将其返回。

时间复杂度：\(O(n)\)，对于含有 n 个元素的链表，我们访问每个元素最多一次。添加一个结点到哈希表中只需要花费 \(O(1)\) 的时间。 空间复杂度：\(O(n)\)，空间取决于添加到哈希表中的元素数目，最多可以添加 \(n\) 个元素

Folyd算法

第一阶段 执行 第141题 代码，利用快慢指针从head出发，慢指针一次走一步，快指针一次走两步，找到相遇点。

第二阶段 给定阶段 1 找到的相遇点，阶段 2 将找到环的入口。首先我们初始化额外的两个指针： ptr1 ，指向链表的头（下图中的 list head）， ptr2 指向相遇点（下图中的 first interaction）。然后，我们每次将它们往前移动一步，直到它们相遇，它们相遇的点就是环的入口，返回这个节点。上述推断的基础是：关系 \(b = F\) 成立。

99987d4e679fdfbcfd206a4429d9b076b46ad09bd2670f886703fb35ef130635-image.png

关于上面这个结论的数学推导过程如下：当快慢指针都是从head出发时，假设相遇时慢指针走了 \(x\) 步，快指针走了 \(y\) 步，则相遇时有 \(2 \times x = y\)，已知 \(x=F+a\)， \(y = F + a + b\)，代入前式可得 \(F = b\)。以上就是Floyd算法的全过程了。

时间复杂度：\(O(n)\) 对有环列表，快指针和慢指针在 \(F+C-h\) 次迭代以后会指向同一个节点，正如上面正确性证明所示，\(F+C-h \leq F+C = n\)，所以阶段 1 运行时间在 \(O(n)\) 时间以内，阶段 2 运行 \(F < n\) 次迭代，所以它运行时间也在 \(O(n)\) 以内。 对于无环链表，快指针大约需要迭代 \(\dfrac{n}{2}\) 次会抵达链表的尾部，这样不会进入阶段 2 就直接退出。 因此，不管是哪一类链表，都会在与节点数成线性关系的时间内运行完。

空间复杂度：\(O(1)\) Floyd 的快慢指针算法仅需要几个指针，所以只需常数级别的额外空间。

剑指offer

  1. 判断是否有环：执行 第141题 代码，利用快慢指针从head出发，慢指针一次走一步，快指针一次走两步，找到相遇点。
  2. 计算环部分的长度 n：如果两个指针相遇，则表明链表中存在环。两个指针相遇的节点一定是在环中。可以从这个节点出发，一边继续向前移动一边计数，当再次回到这个节点时，就可以得到环中节点数了。
  3. 找到环入口：快慢指针回到开始点，快指针领先慢指针 n 个节点之后，快慢指针都以一次一步的方式向前移动，两个指针相遇之处，就是链表入口。

代码

基于hash map

1
2
3
4
5
6
7
8
9
10
class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        nodesSee = list()
        while head:
            if head in nodesSee:
                return head
            else:
                nodesSee.append(head)
            head = head.next
        return None

Floyd算法

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def getEncounter(self, head: ListNode) -> ListNode:
        # 注意，slow和fast和第142题不再一样了，都是从head这里出发的了。
        slow = head
        fast = head

        # 由于 slow 和 fast一开始就都是从head开始出发的，这个while条件 slow != fast 就不会满足，所以不能这么写。
        # 得用 fast != None and fast.next != None 做while条件，用 slow == fast 做终止条件，如下面那部分代码所示。
        # while slow != fast:
        #     if fast == None or fast.next == None:
        #         return None
        #     slow = slow.next
        #     fast = fast.next.next
        # return slow

        while fast != None and fast.next != None:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                return slow
        return None

    def detectCycle(self, head: ListNode) -> ListNode:
        if head == None or head.next == None:  return None
        # Floyd算法
        # 第一阶段 获取相遇点
        encounter = self.getEncounter(head)
        if not encounter:  return None  # 不相遇说明不是环

        # 第二阶段
        # 给定阶段 1 找到的相遇点，阶段 2 将找到环的入口。首先我们初始化额外的两个指针： `ptr1` ，指向链表的头（下图中的 list head）， `ptr2 ` 指向相遇点（下图中的 first interaction）。然后，我们每次将它们往前移动一步，直到它们相遇，它们相遇的点就是环的入口。
        ptr1 = head
        ptr2 = encounter
        while ptr1 != ptr2:
            ptr1 = ptr1.next
            ptr2 = ptr2.next
        return ptr1

剑指offer

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def isCycle(self, head):
        # 第一种写法
        fast = head
        slow = head
        while fast and fast.next and fast.next:
            fast = fast.next.next
            slow = slow.next
            if fast == slow:
                return slow
        return False
        # # 第二种写法
        # slow = head
        # fast = head.next
        # while slow != fast:
        #     if fast == None or fast.next == None:
        #         return False
        #     slow = slow.next
        #     fast = fast.next.next
        # return slow

    def detectCycle(self, head: ListNode) -> ListNode:
        if head == None or head.next == None:  return None  # 空链表和只有一个节点的链表判断 
        # stage 1
        meet = self.isCycle(head)
        if meet:
            # stage 2
            p = meet.next
            count = 1  # p = meet.next时，已经往后面走了一步了。
            while p!=meet:
                p = p.next
                count += 1
            # stage 3
            slow = head
            fast = head
            while count:
                fast = fast.next
                count -= 1
            while fast != slow:
                fast = fast.next
                slow = slow.next
            return fast
        else:
            return None