欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-06-17 17:20:49
...

题目描述

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

思路:

step1:如何确定一个链表中包含环?

可以定义两个指针,一个快,一个慢,同时从链表头结点开始,慢指针一次走一步,快指针一次走2步。如果快指针和慢指针相遇,则说明链表中包含环。如果慢指针到链表末尾,都没和快指针相遇,则链表中不包含环。

step2:如何找到环的入口?

定义两个指针p1,p2指向链表头结点。如果环中有n个结点,则指针P1在链表上先移动n位,然后2个指针以相同的速度向前移动,当第2个指针走到环的入口节点时,第1个指针已经围绕着环走了一圈,再次回到入口节点。

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

实现1:

/*
 public class ListNode {
    int val;
    ListNode next = null;
 
    ListNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
    public ListNode MeetNode(ListNode pHead){
        if(pHead==null){
            return null;
        }
        ListNode slow=pHead.next;
        if(slow==null){
            return null;
        }
        ListNode fast=slow.next;
        if(fast==null){
            return null;
        }
        while(fast!=null&&slow!=null){
            if(fast==slow){
                return fast;
            }
            slow=slow.next;
            fast=fast.next;
            if(fast!=null){
                fast=fast.next;
            }
        }
        return null;
    }
 
    public ListNode EntryNodeOfLoop(ListNode pHead){
        ListNode meetNode=MeetNode(pHead);
        if(meetNode==null){
            return null;
        }
        //得到环中的节点数目
        int nodeInLoop=1;
        ListNode pNode1=meetNode;
        while(pNode1.next!=meetNode){
            pNode1=pNode1.next;
            ++nodeInLoop;
        }
        //先移动pNode1,移动次数为环中节点数目
        pNode1=pHead;
        for(int i=0;i<nodeInLoop;++i){
            pNode1=pNode1.next;
        }
        //再移动pNode1和pNode2,直到相遇
        ListNode pNode2=pHead;
        while(pNode1!=pNode2){
            pNode1=pNode1.next;
            pNode2=pNode2.next;
        }
        return pNode1;
         
    }
}

 

思路2:

参考https://blog.csdn.net/snow_7/article/details/52181049

两个指针一个fast、一个slow同时从一个链表的头部出发
 fast一次走2步,slow一次走一步,如果该链表有环,两个指针必然在环内相遇 此时只需要把其中的一个指针重新指向链表头部,另一个不变(还在环内),这次两个指针一次走一步,相遇的地方就是入口节点。

此问题包含两个步骤:

(1)判断链表中是否有环

(2)找出环

1)选择快慢指针,让快指针每次走两步,慢指针每次走一步,若是单链表中有环的话,那么两个指针会相遇,即指向的相同的节点的值相等来判断。

2)当相遇的时候,慢指针在环中走了k步,设环之外的部分长为x,环的长度为n,则快指针一共走了 x+m*n步,(m为快指针在环中走的圈数),慢指针一共走了x+k步,因为快指针的速度是慢指针的两倍。那么可以得到2(x+k)=x+m*n+k;得到x为m*n-k ,慢指针在圈中还剩下的步数n-k;

二、

让快指针从头开始,两个指针每次都走一步,当快指针走了想x(m*n-k)步的时候,到达环的入口,慢指针在圈中走m-1圈加k步的时候,也到达环入口那个节点,两个指针再次相遇,此刻的节点就是环的入口的节点。
剑指offer:链表中环的入口节点

 

实现2:推荐使用方法

先说个定理:两个指针一个fast、一个slow同时从一个链表的头部出发
     * fast一次走2步,slow一次走一步,如果该链表有环,两个指针必然在环内相遇
     * 此时只需要把其中的一个指针重新指向链表头部,另一个不变(还在环内),
     * 这次两个指针一次走一步,相遇的地方就是入口节点。

/*
 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){
            return null;
        }
        ListNode fast=pHead;
        ListNode slow=pHead;
        while(fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
            if(fast==slow){
                break;
            }
        }
        if(fast==null||fast.next==null){
            return null;
        }
        fast=pHead;
        while(fast!=slow){
            fast=fast.next;
            slow=slow.next;
        }
        return fast;
    }
}

 

实现3:利用hashmap保存链表中的节点

/*
 public class ListNode {
    int val;
    ListNode next = null;
 
    ListNode(int val) {
        this.val = val;
    }
}
*/
import java.util.HashMap;
public class Solution {
 
    public ListNode EntryNodeOfLoop(ListNode pHead)
    {
        HashMap<Integer,Integer> hs=new HashMap<>();
        while(pHead!=null){
            if(!hs.containsKey(pHead.val)){
                hs.put(pHead.val,1);
            }else{
                return pHead;
            }
            pHead=pHead.next;
        }
        return null;
    }
}