关注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

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

17 − 5 =