关注Java领域相关技术 记录有趣的事情

LeetCode-142. 环形链表 II

US-B.Ralph
US-B.Ralph
2020-10-10

问题地址

LeetCode每日一题/2020-10-10

LeetCode142. 环形链表 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
解释:链表中没有环。

说明:

  • 不允许修改给定的链表。

进阶

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


解析

解题思路

  • 哈希表
    • 遍历链表,使用哈希表存储链表节点,当存在环时(遇到此前遍历过的节点),也就找到了环入口;
  • 快慢指针

    • 根据141. 环形链表,使用快慢指针可以判断链表是否有环。
    • 当判断出环中有环接下来如何找出环的入口呢?
      • 根据上图我们可以知道快慢指针相遇时fast走过的节点数为 x+n(y+z)+y,其中n为fast指针走过的环数,由于fast必定走过1圈才能遇到slow指针,故 n >= 1
      • slow指针走过的节点数为 x+y
      • 根据快慢指针移动速度我们知道fast走过的节点数量时slow走过的节点数量的2倍,故有x+n(y+z)+y=2(x+y),得出x=n(y+z)-y,整理后得出x=(n-1)(y+z)+z
      • 我们分析整理后的公式x=(n-1)(y+z)+z可以发现,当n=1时,x=z,这意味着从head节点出发一个节点,同时从环中相遇点出发一个节点,两个节点每次移动1个节点,那么当这两个节点将在入环点相遇

数据操作分析

  • 见思路分析

复杂度分析

  1. 时间复杂度
  2. 空间复杂度

编码实现

  • 哈希表
public class LeetCode0142_LinkedListCycleii {
    public ListNode detectCycle(ListNode head) {
        Map<ListNode, ListNode> map = new HashMap();
        while (head != null) {
            if (map.containsKey(head)) return map.get(head);
            map.put(head, head);
            head = head.next;
        }
        return null;
    }
}
  • 快慢指针
public class LeetCode0142_LinkedListCycleii_2 {
    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null) return null;
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null) {
            slow = slow.next;
            if (fast.next == null) {
                return null;
            } else {
                fast = fast.next.next;
            }
            if (slow == fast) {
                ListNode pre = head;
                while (pre != slow) {
                    pre = pre.next;
                    slow = slow.next;
                }
                return pre;
            }

        }

        return null;
    }
}

官方解法

方法一:哈希表

思路与算法:

  • 思路与算法
  • 一个非常直观的思路是:我们遍历链表中的每个节点,并将它记录下来;一旦遇到了此前遍历过的节点,就可以判定链表中存在环。借助哈希表可以很方便地实现。

复杂度分析:

  1. 时间复杂度:O(N)。其中 N 为链表中节点的数目。我们恰好需要访问链表中的每一个节点。
  2. 空间复杂度:O(N)。其中 N 为链表中节点的数目。我们需要将链表中的每个节点都保存在哈希表当中。

编码实现

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode pos = head;
        Set<ListNode> visited = new HashSet<ListNode>();
        while (pos != null) {
            if (visited.contains(pos)) {
                return pos;
            } else {
                visited.add(pos);
            }
            pos = pos.next;
        }
        return null;
    }
}

方法二:快慢指针

思路及算法:

  • 我们使用两个指针,\textit{fast}\textit{slow}。它们起始都位于链表的头部。随后,\textit{slow} 指针每次向后移动一个位置,而 \textit{fast} 指针向后移动两个位置。如果链表中存在环,则 \textit{fast} 指针最终将再次与 \textit{slow} 指针在环中相遇。
  • 如下图所示,设链表中环外部分的长度为 a。\textit{slow} 指针进入环后,又走了 b 的距离与 \textit{fast} 相遇。此时,\textit{fast} 指针已经走完了环的 n 圈,因此它走过的总距离为 a+n(b+c)+b=a+(n+1)b+nc

  • 根据题意,任意时刻,\textit{fast}fast 指针走过的距离都为 \textit{slow}slow 指针的 22 倍。因此,我们有

$$
a+(n+1)b+nc=2(a+b) \implies a=c+(n-1)(b+c)
a+(n+1)b+nc=2(a+b)⟹a=c+(n−1)(b+c)
$$

  • 有了 a=c+(n-1)(b+c) 的等量关系,我们会发现:从相遇点到入环点的距离加上 n-1 圈的环长,恰好等于从链表头部到入环点的距离。
  • 因此,当发现 \textit{slow}\textit{fast} 相遇时,我们再额外使用一个指针 \textit{ptr}。起始,它指向链表头部;随后,它和 \textit{slow} 每次向后移动一个位置。最终,它们会在入环点相遇。

复杂度分析:

  1. 时间复杂度:O(N),其中 N 为链表中节点的数目。在最初判断快慢指针是否相遇时,\textit{slow} 指针走过的距离不会超过链表的总长度;随后寻找入环点时,走过的距离也不会超过链表的总长度。因此,总的执行时间为 O(N)+O(N)=O(N)

  2. 空间复杂度:O(1)。我们只使用了 \textit{slow}, \textit{fast}, \textit{ptr} 三个指针。

编码实现

public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode slow = head, fast = head;
        while (fast != null) {
            slow = slow.next;
            if (fast.next != null) {
                fast = fast.next.next;
            } else {
                return null;
            }
            if (fast == slow) {
                ListNode ptr = head;
                while (ptr != slow) {
                    ptr = ptr.next;
                    slow = slow.next;
                }
                return ptr;
            }
        }
        return null;
    }
}

精彩评论

跳转地址1:环形链表 II(双指针法,清晰图解)

前言

  • 这类链表题目一般都是使用双指针法解决的,例如寻找距离尾部第K个节点、寻找环入口、寻找公共尾部入口等。

算法流程:

  • 双指针第一次相遇: 设两指针 fast,slow 指向链表头部 head,fast 每轮走 2 步,slow 每轮走 1 步;

    • 第一种结果: fast 指针走过链表末端,说明链表无环,直接返回 null;
      • TIPS: 若有环,两指针一定会相遇。因为每走 1 轮,fast 与 slow 的间距 +1,fast 终会追上 slow;
    • 第二种结果: 当 fast == slow 时, 两指针在环中 第一次相遇 。下面分析此时fast 与 slow走过的 步数关系 :
      • 设链表共有 a+b 个节点,其中 链表头部到链表入口 有 a 个节点(不计链表入口节点), 链表环 有 b 个节点(这里需要注意,a 和 b 是未知数,例如图解上链表 a=4 , b=5);设两指针分别走了 f,s 步,则有:
        • fast 走的步数是slow步数的 2 倍,即 $f = 2s4;(解析: fast 每轮走 2 步)
        • fast 比 slow多走了 n 个环的长度,即 f = s + nb;( 解析: 双指针都走过 a 步,然后在环内绕圈直到重合,重合时 fast 比 slow 多走 环的长度整数倍 );
      • 以上两式相减得:f = 2nb,s = nb,即fast和slow 指针分别走了 2n,n 个环的周长 (注意: n 是未知数,不同链表的情况不同)。
  • 目前情况分析:
    • 如果让指针从链表头部一直向前走并统计步数k,那么所有 走到链表入口节点时的步数 是:k=a+nb(先走 a 步到入口节点,之后每绕 1 圈环( b 步)都会再次到入口节点)。
    • 而目前,slow 指针走过的步数为 nb 步。因此,我们只要想办法让 slow 再走 a 步停下来,就可以到环的入口。
    • 但是我们不知道 a 的值,该怎么办?依然是使用双指针法。我们构建一个指针,此指针需要有以下性质:此指针和slow 一起向前走 a 步后,两者在入口节点重合。那么从哪里走到入口节点需要 aa 步?答案是链表头部head。
  • 双指针第二次相遇:
    • slow指针 位置不变 ,将fast指针重新 指向链表头部节点 ;slow和fast同时每轮向前走 11 步;
      • TIPS:此时 f = 0,s = nb
    • 当 fast 指针走到f = a 步时,slow 指针走到步s = a+nb,此时 两指针重合,并同时指向链表环入口 。
  • 返回slow指针指向的节点。

复杂度分析:

编码实现
public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head, slow = head;
        while (true) {
            if (fast == null || fast.next == null) return null;
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) break;
        }
        fast = head;
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        return fast;
    }
}
US-B.Ralph
LeetCode数据结构与算法算法

Leave a Comment

邮箱地址不会被公开。 必填项已用*标注