[数据结构与算法]JZ23 链表中环的入口结点

JZ23 链表中环的入口结点

描述

给一个长度为n链表，若其中包含环，请找出该链表的环的入口结点，否则，返回null。

数据范围：n ≤ 1000；

要求：空间复杂度O(1)，时间复杂度O(n)。

示例1

输入：

{1,2},{3,4,5}

返回值：

3

**说明：**返回环形链表入口节点，我们后台会打印该环形链表入口节点，即3。

示例2

输入：

{1},{}

返回值：

"null"

**说明：**没有环，返回null，后台打印"null"

解析

这题初见是真的毫无思路，无从下手，在看了题解后才恍然大悟，所以通过这篇笔记记录一下思路。
要找到链表中环的入口节点，需要经过三步：判断链表是否有环、求出环的长度、找到环的入口。

判断链表是否有环

先判断链表中是否有环，若有环则进行后面的操作，若无环则直接返回 null。此处我们可以采取设置快慢两个指针的方式来进行这个判断。快慢指针都从头开始走，快指针一次走两步，慢指针一次走一步，若有环，则两指针必相遇（追及问题），若无环，则快指针会先走到空。

求出环的长度

这一步是为后面进行铺垫，到这步说明链表中存在环，且此时快慢指针在环中的相同位置（追上了）。故此时让慢指针继续一步步走，每走一步计数值加一，再次遇到快指针时停止，此时的计数值就是环的节点数，即环的长度。

找到环的入口

有了前面的数据，就能找到环的入口了，这是非常巧妙的一步。
首先，将快慢指针重置到链表头部，让快指针先走N步，N为链表环的长度，然后再让慢指针和快指针一起一步步走，当两指针相遇时，所在之处就是环的入口。

原理分析：设链表除环之外的长度为X，则链表的实际节点数应为X+N，第X+1个节点就是环的入口，且该节点与第X+1+N个节点是同一个节点（相当于从入口处走了一个环的长度）；快指针先走了N步，处于第1+N个节点，此时慢指针处于第1个节点，这时候它们同步开始走，经过X个节点后，快指针处于第1+N+X个节点，慢指针处于第1+X个节点，即它们在同一个位置，环的入口。

代码清单

/*
 public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {

    public ListNode EntryNodeOfLoop(ListNode pHead) {
        // 1.判断链表中有无环：快慢指针相遇
        ListNode slow = pHead;
        ListNode fast = pHead;
        boolean flag = false;
        int num = 0;
        // 判断快指针是否走完即可
        while( fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
            if( slow == fast && slow != null){
                flag = true;
                break;
            }
        }
        // 2.得到环中节点数量
        if(flag == false){
            // 没有环
            return null;
        }else{
            // 有环
            num += 1;
            slow = slow.next;
            while( slow != fast){
                num += 1;
                slow = slow.next;
            }
        }
        // 3.寻找环的入口：快指针先一步步地走环的节点数 n 步，慢指针再开始走
        // 因为有环的存在，所以快慢指针必在环的入口相遇（快指针先走的n步会在环中消耗掉
        fast = pHead;
        slow = pHead;
        for( int i = 0; i < num; i++){
            fast = fast.next;
        }
        while( slow != fast){
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }
}

总结

这道题代表了一种解题思路，即将问题拆分成多个问题逐个解决。先判断是否有环，是第一个问题；若有环则要找环的入口，是第二个问题；找环的入口可以通过环的性质实现，是第三个问题。

当然解题的思路也是看了答案才知道的，不过，这篇笔记的意义就在于以后能轻松写出这种题目！