链表中环的入口结点(剑指offer)

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

 

方法一:双指针

分析:首先用双指针就能探测出链表是否有换,如果有环,两个指针肯定会相遇 的。
a是头结点到入口结点的距离,b是入口节点Y到相遇处Z的距离,c是环的长度减去b。
相遇时有:
S_{fast} = 2S_{slow}
假设相遇时pFast在环内转了k圈,则
a + k(b+c) + b = 2(a + b) 
移项得:
a = (k-1)(b+c) + c
说明头结点X到入口结点Y的距离等于从相遇处Z开始在环内转悠k-1圈(k >= 1)后,最后从Z到Y的距离。当k =1时候,a = c,此时pFast比pSlow多走一圈

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

    ListNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
    public ListNode EntryNodeOfLoop(ListNode pHead) {
        if(pHead==null||pHead.next==null) return null;
        ListNode slow=pHead;
        ListNode fast=pHead;
        while (fast!=null||fast.next!=null){
            slow=slow.next;
            fast=fast.next.next;
            if(slow==fast){
                fast=pHead;
                while (slow!=fast){
                    fast=fast.next;
                    slow=slow.next;
                }
            }
            if(slow==fast)
                return fast;
        }
        return null;
    }
}

 

上一篇:输出链表倒数第K个元素的节点值


下一篇:剑指offer-复杂链表的复制-Python