leetcode 142. 环形链表 II

题目描述

给定一个链表，返回链表开始入环的第一个节点。如果链表无环，则返回 null。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。
说明：不允许修改给定的链表。
相关话题： 链表、双指针 难度： 中等

示例 1：

示例 2：

示例 3：

进阶：
你是否可以不用额外空间解决此题？
思路：这道题需要先确定链表有环，方法同leetcode 141. 环形链表。

定义两个指针，慢指针slow和快指针fast，慢指针一次走一步，快指针一次走两步；
当慢指针和快指针重合，即slow == fast，确定链表有环，此时慢指针slow回到链表头部，快指针fast和慢指针slow每次走一步，当慢指针和快指针再次重合，重合的节点就是环的入口节点。

证明：

如图，无环部分长度为 L，有环部分长度为R，第一次相遇指针离入环节点距离为C。
假设t时刻，slow和fast指针相遇，则

两式相减， $t = (k_2 - k_1)R$ ，可以看出slow指针和fast指针的距离为环长度的倍数，那么它们必定会在某个时刻相遇。
证明它们会相遇之后，我们反证法证明第二次相遇的位置就是环的入口节点。
已知它们t时刻会在入口节点相遇，

整理得， $L = kR - C$ 。可以理解为fast指针比slow指针领先了C步， $kR-C$ 看成fast指针退后C步出发，slow指针从链表头出发，刚好相差kR，也就是说slow走过L来到入口节点时，fast也在入口节点，不矛盾。

/**
 * 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)
            return null;
        ListNode slow = head;
        ListNode fast = head;
        //slow一次走一步，fast一次走两步，如果相遇就是有环
        while(fast.next != null&&fast.next.next != null){
            slow = slow.next;
            fast = fast.next.next;
            //有环
            if(slow == fast){
                slow = head;//slow指针回到head
                //slow和fast变成每次走一步，相遇时就是入口节点
                while(slow != fast){
                    slow = slow.next;
                    fast = fast.next;
                }
                return slow;
            }
        }
        return null;
    }
}

最后编辑于：2019.05.29 17:38:36