剑指Offer-链表中环的入口结点

曾经终败给现在 2022-02-14 03:22 191阅读 0赞

## 题目描述 ##

给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。

解题思路—**HashMap**：使用HashMap存储链表结点，当链表结点重复时，即有环时，输出当前结点即可。  
解题思路—**快慢指针**：这里有一个可以判断链表是否有环并且找到环入口的既定方法，这个**方法很巧妙**：

> **设置两个指针pfast和pslow，同时从链表头出发，pfast一次走两步，pslow一次走一步，如果链表有环，则两个指针必定会在环内相遇。此时只要一个指针重新指向链表头部，另外一个指针在相遇结点，同时出发，一次走一步，它们相遇的结点就是环入口结点。**

这个定理如何证明呢，以下是**证明过程**：

> **设链表头至环入口结点的距离为x，环入口至pfast和pslow相遇结点的距离为a，环的总长为c。**  
> **当pfast和pslow相遇时，pslow走过的路程为 `x + m*c + a`，pfast走过的路程为`x + n*c + a`。因为pfast的速度是pslow的两倍，所以`2*(x + m*c + a) = x + n*c + a`，即`x = (n - 2 * m )*c - a = (n - 2 *m -1 )*c + c - a`。  
> `c - a`为环内一圈剩余的路程，`(n - 2 *m -1 )*c`为环的总长的`(n - 2 *m -1 )`倍，所以现在只需要一个指针指向链表头，另一个指针在相遇结点，同时出发一次一步，当它们相遇时，即走过了x路程长，相遇的结点就是环入口结点。**

## Java解题—HashMap ##

import java.util.HashMap;
    public class Solution {
        public ListNode EntryNodeOfLoop(ListNode pHead)
        {
            HashMap<ListNode, Integer> map = new HashMap<>();
            while(pHead!=null){
                if(map.containsKey(pHead))
                    return pHead;
                map.put(pHead, null);
                pHead = pHead.next;
            }
            return null;
        }
    }

## Java解题—快慢指针 ##

public class Solution {
        public ListNode EntryNodeOfLoop(ListNode pHead)
        {
            ListNode pfast = pHead;
            ListNode pslow = pHead;
    
            while(pfast!=null && pfast.next!=null){
                pfast = pfast.next.next;
                pslow = pslow.next;
                if(pfast==pslow)
                    break;
            }
            
            if(pfast==null || pfast.next==null)
                return null;
            
            while(pHead!=pslow){
                pHead = pHead.next;
                pslow = pslow.next;
            }
            return pHead;
        }
    }