剑指offer:链表中环的入口节点
题目描述
给一个链表,若其中包含环,请找出该链表的环的入口结点,否则,输出null。
思路:
step1:如何确定一个链表中包含环?
可以定义两个指针,一个快,一个慢,同时从链表头结点开始,慢指针一次走一步,快指针一次走2步。如果快指针和慢指针相遇,则说明链表中包含环。如果慢指针到链表末尾,都没和快指针相遇,则链表中不包含环。
step2:如何找到环的入口?
定义两个指针p1,p2指向链表头结点。如果环中有n个结点,则指针P1在链表上先移动n位,然后2个指针以相同的速度向前移动,当第2个指针走到环的入口节点时,第1个指针已经围绕着环走了一圈,再次回到入口节点。
实现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步的时候,也到达环入口那个节点,两个指针再次相遇,此刻的节点就是环的入口的节点。
实现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;
}
}
推荐阅读