剑指offer链表中环的入口节点

剑指offer链表中环的入口节点

目录

描述

方法一 Hash法

方法二 快慢指针

---

描述

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

数据范围： n≤10000nle10000n≤10000，1<=结点值<=100001<=结点值<=100001<=结点值<=10000

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

例如，输入{1,2},{3,4,5}时，对应的环形链表如下图所示：

可以看到环的入口结点的结点值为3，所以返回结点值为3的结点。

这道题有两种方法

方法一 Hash法

方法一就是使用set集合去记录已经走过的节点，当发现再次走到这个节点时就说明这个是环的入口，如果到了null就说明没有环

java代码

public ListNode EntryNodeOfLoop(ListNode pHead) {
        if(pHead==null)return null;
        Set set=new HashSet<>();
        while(pHead!=null){
            if(!set.contains(pHead)) set.add(pHead);
            else return pHead;
            pHead=pHead.next;
        }
        return null;
    }

方法二 快慢指针

 第二种方法则是通过快慢指针来实现，定义一个快指针p1，每次走一步，一个慢指针p2，每次走两步，当两个指针相遇时，就说明有环，而他们相遇的节点是在环内，此时p1走的步数是p2的两倍，假设链表是1-2-3-4-5，环是3-4-5，那么p1和p2会在4相遇

假设1-2是x，3-4是y，p2走的步数是x+y，p1是p2的两倍，为2x+2y

p1走的节点为1-2-3-4-5-3-4，p2走的节点为1-2-3-4，p1比p2多走了4-5-3-4，

则4-5-3的步数为2x+2y-x-y-y=x，所以4-5-3=1-2,如下图

 java代码

public ListNode EntryNodeOfLoop(ListNode pHead) {
        if(pHead==null)return null;
        ListNode p1=pHead;
        ListNode p2=pHead;
        while (p1!=null&&p2!=null){
            if(p1.next==null)return null;
            p1=p1.next.next;
            p2=p2.next;
            if(p1==p2)break;
        }
        if(p1==null||p2==null)return null;
        while(pHead!=p1){
            pHead=pHead.next;
            p1=p1.next;
        }
        return p1;
    }