环形链表 II

发表于
本文字数： 1.7k 阅读时长 ≈ 2 分钟

LeetCode每日一题，142. 环形链表 II

先看题目描述

大意就是给定一个链表，若链表中有环，就让我们返回环的起点；否则，就返回空

算法和思路

这类链表题目一般使用双指针解决

算法流程

  1. 双指针第一次相遇：设两指针 fast 和 slow 指向 head，fast 每轮走两步，slow 每轮走一步
    1. 第一种结果：fast 指针走过链表末端，说明无环，返回 null
    2. 第二种结果：当 fast == slow 时，两指针第一次在环中相遇，下面分析 fast 和 slow 走过的步数的关系
      • 设链表共有 a+b 个节点，其中 链表头部到链表环的入口 有 a 个节点（不计链表入口节点）， 链表环 有 b 个节点；设两指针分别走了 f，s 步，则有：
        1. fast 走的步数是 slow 的两倍，f = 2s
        2. fast 比 slow 多走了 n 个环的长度，即 f = s +nb
      • 两式相减得 f = 2nb，s = nb，即 f 和 s 分别走了 2n，n 个环的周长
  2. 目前情况分析
    • 如果让指针从链表头部一直向前走并统计步数 k，那么所有走到链表环的入口节点时的步数是：k=a+nb（先走 a 步到入口节点，之后每绕 1 圈环（ b 步）都会再次到入口节点）
    • 而目前，slow 指针走过的步数为 nb 步。因此，我们只要想办法让 slow 再走 a 步停下来，就可以到环的入口
    • 但是我们不知道 a 的值，该怎么办？依然是使用双指针法。我们构建一个指针，此指针需要有以下性质：此指针和 slow 一起向前走 a 步后，两者在链表环的入口节点相遇。那么从哪里走到链表环的入口节点需要 a 步？答案是链表头部head
  3. 双指针第二次相遇：
    • slow 指针位置不变 ，将 fast 指针重新 指向链表头部节点 head；slow 和 fast 同时每轮向前走 1 步
    • 当 fast 指针走到 f = a 步时，slow 指针走到 s = a + nb 步；此时两指针重合，并同时指向链表环入口
  4. 返回 slow 指针指向节点

算法源码

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
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null) {
            slow = slow.next;
            fast = fast.next;
            if (fast == null) return null;
            fast = fast.next;
            if (slow == fast) {
                fast = head;
                while (slow != fast) {
                    slow = slow.next;
                    fast = fast.next;
                }
                return slow;
            }
        }
        return null;
    }
}