142. 环形链表 II

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

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

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

示例 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
解释:链表中没有环。

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

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/linked-list-cycle-ii

解题思路:
方法一:暴力法
主要想法是,一个一个的进行遍历,每遍历一个,就判断该结点是否在 序列 res 中,不在就将其添加进序列,否则返回该结点。
代码如下:

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        if not head:
            return None
        res = [head]
        node = head.next
        while node:
            if node in res:
                return node
            res.append(node)
            node = node.next
        return None

方法二:快慢指针
设慢指针slow每次只走一个单位距离,快指针fast每次走两个单位距离 --> slow = slow.next, fast = fast.next.next。两个指针都从起始位置开始走。从起点到入环点的距离我们设为 a,从入环点到他们第一次在环中相遇的点的距离设为b,则环的另一段设为c,走过的圈数为n。因为fast的速度是slow的两倍,所以相同时间内fast走过的路程是slow的两倍。则有,(a+b) * 2 = a + (b+c)n + b --> (a+b) * 2 = a + (n+1)b + nc  --> a = c + (n-1)b 。
从最后一个式子我们可以推导出,从链表的起始点走过距离 a 和在环中走过的 c + (n-1)b 的距离相等,且此时会在入环点相遇,因为(n-1)b相当于走了 b 个圈,最后还是会走 c 的距离,这样我们就能得到最后的入环点。代码如下:

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return None
        fast = head
        slow = head
        pst = head
        while True:
            fast = fast.next.next
            slow = slow.next
            if not fast or not fast.next:
                break
            if fast == slow:
                while True:
                    if fast == pst:
                        return fast
                    fast = fast.next
                    pst = pst.next

        return None
点赞
  1. erotik izle说道:

    If you want to use the photo it would also be good to check with the artist beforehand in case it is subject to copyright. Best wishes. Aaren Reggis Sela

  2. erotik说道:

    Thanks for sharing, this is a fantastic blog. Want more. Helen-Elizabeth Lindsey Santoro

发表评论

Title - Artist
0:00