Leetcode 142.环形链表II

Posted on |

142.环形链表II

题目

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：tail connects to node index 1
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

输入：head = [1,2], pos = 0
输出：tail connects to node index 0
解释：链表中有一个环，其尾部连接到第一个节点。


示例 3：

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

方法

方法1

参考资料，请看图
快慢指针，快指针走两步，慢指针走一步。链表的起点是A，环的入口是B，相遇点是C。顺时针

  • A到B的距离为X
  • B到C的距离为Z
  • C到B的距离为Y
  • 环的长度为L

即。这就意味这，slow和fast相遇后，slow在相遇点C。此时head和slow分别从A和C出发，步长为1，当slow在C点出发多走(n-1)圈（距离(n-1)L+Y)，会与在起点A出发的head相遇，此时相遇点就是换的入口点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 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
        """
        slow=fast=head
        while fast and fast.next:
            slow=slow.next
            fast=fast.next.next
            if slow==fast:
                while slow!=head:
                    slow=slow.next
                    head=head.next
                return slow
        # return -1

return None 可以是直接不返回