White's Studio.

LeetCode 142. Linked List Cycle II

LeetCode
2019/09/23 Share

LeetCode 142. Linked List Cycle 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
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

这道题是比较经典的链表题： 快慢指针。

讲快慢指针前， 需要讲一下一道小学题：环形追击

环形跑道的周长是800米，甲、乙两名运动员同时顺时针自起点出发，甲的速度是每分钟400米，乙的速度是每分钟375米，多少分钟后两人第一次碰面?甲、乙两名运动员各跑了多少米?甲、乙两名运动员各跑了几圈?

这就是一道典型的环内追击问题， 这里有个很容易想象的原理，当慢速员（乙）被快速员（快）追上的时候，慢速员（乙）只能落后快速员（甲）一圈，快速员（甲）只能领先慢速员（乙）一圈。

所以 环形周长 = （快速员速度 - 慢速员速度）* 时间

回到我们的快慢指针，当两个指针都在环的时候， 快指针 如果 需要追上 慢指针， 则需要领先快指针 c（环长） + (快指针 - 慢指针 的距离)

回到我们这个题目：

  1. 如果到达了链表的尾部， 就会出现 null 节点， 那么这个链表就不会成环
  2. 如果链表的尾部成环，那么我们设定的快慢指针总会相遇； 而追上的时候， 就是 快指针 需要 领先 慢指针的距离 = 环周长 + （慢指针 出发时 快指针距离慢指针的距离 == 慢指针入环前走的距离）

解题： 假设快指针fast 速度 为 q ， 慢指针 slow 速度 为 p ， 链表头距离环入口距离为 m， 环周长为 l

快指针是慢指针速度的 n 倍， q = np；

如果 链表成环时， fast 走的距离 是 Q， slow 走的距离是 P， Q = nP；

那么 Q - P = l + （l - m）

​ nP - P = 2l - m

​ (n-1)P = 2l - m 这里说明了， 第一次相遇时 fast 和 slow 在环的位置 肯定就是 距离入环处 距离为 m， 所以只要 再 重新走 距离 m 就能找到 入环口。

反过来说， 首先让快指针 慢下来 跟 慢指针速度一致， 然后让快指针冲链表头出发， 那么相遇的地方就是环的入口了。

附上算法.

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
33
/**
 * 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) {
        if (head == null || head.next == null) {
          return null;
        }
        ListNode fast = head.next.next;
        ListNode slow = head.next;
        while (fast != null && fast.next != null) {
          fast = fast.next.next;
          slow = slow.next;
          if (slow == fast) {
            slow = head;
            while (slow != fast) {
              slow = slow.next;
              fast = fast.next;
            }
            return slow;
          }
        }
        return null;
    }
}

备注： 这里的快指针一般指为慢指针的两倍速度， 原因就是进入循环前 只用 判断前两个节点是否为空， 当然也可以设置其他倍数， 也要注意进入循环前， 需要判断多几个节点 是否为空就好。

原文作者: White

原文链接: http://yuchenzhen.github.io/2019/09/23/LeetCode-142-Linked-List-Cycle-II/

发表日期: September 23rd 2019, 11:03:59

版权声明: 本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG
  1. 1. LeetCode 142. Linked List Cycle II
Total : 31
2019
2018
Java Binary_Tree Python Node.js RPC git List Leetcode Leedcode LeetCode LintCode Node.js dubbo electron Java Spring-boot hexo 脑洞题 消息队列 Leetcode Java 数据结构，二叉树 Algorithm