首页 > 试题广场 > 链表中环的入口结点
[编程题]链表中环的入口结点
给一个链表,若其中包含环,请找出该链表的环的入口结点,否则,输出null。
推荐
如果链表中 有n个结点,指针P1在链表上向前移动n步,然后两个指针以相同的速度向前移动。
 当第二个指针指向环的入口结点时,第一个指针已经围绕着环走了一圈又回到了入口结点。
所以首先要得到环中结点的数目

public class 链表中环的入口结点 {
	//找到一快一满指针相遇处的节点,相遇的节点一定是在环中
	public static ListNode meetingNode(ListNode head) {
		if(head==null)
			return null;
		
        ListNode slow = head.next;
        if(slow==null)
        	return null;
        
        ListNode fast = slow.next;
        while (slow != null && fast != null) {
        	if(slow==fast){
        		return fast;
        	}
        	slow=slow.next;
        	fast=fast.next;
        	
        	if(fast!=slow){
        		fast=fast.next;
        	}
        }
		return null;
    }
	public ListNode EntryNodeOfLoop(ListNode pHead) {
		ListNode meetingNode=meetingNode(pHead);
		if(meetingNode==null)
			return null;
//		得到环中的节点个数
		int nodesInLoop=1;
		ListNode p1=meetingNode;
		while(p1.next!=meetingNode){
			p1=p1.next;
			++nodesInLoop;
		}
//		移动p1
		p1=pHead;
		for(int i=0;i<nodesInLoop;i++){
			p1=p1.next;
		}
//		移动p1,p2
		ListNode p2=pHead;
		while(p1!=p2){
			p1=p1.next;
			p2=p2.next;
		}
		return p1;
	}
}

编辑于 2015-08-25 11:27:14 回复(33)
【转】
http://kekecv.com/2016/06/08/Linked-List-Cycle-%E5%88%A4%E6%96%AD%E9%93%BE%E8%A1%A8%E6%98%AF%E5%90%A6%E6%9C%89%E7%8E%AF%EF%BC%8C%E5%A6%82%E6%9E%9C%E6%9C%89%E7%8E%AF%EF%BC%8C%E6%89%BE%E5%88%B0%E7%8E%AF%E7%9A%84%E5%85%A5%E5%8F%A3/

假设x为环前面的路程(黑色路程),a为环入口到相遇点的路程(蓝色路程,假设顺时针走), c为环的长度(蓝色+橙色路程)

当快慢指针相遇的时候:

此时慢指针走的路程为Sslow = x + m * c + a
快指针走的路程为Sfast = x + n * c + a
2 Sslow = Sfast
2 * ( x + m*c + a ) = (x + n *c + a)
从而可以推导出:
x = (n - 2 * m )*c - a
= (n - 2 *m -1 )*c + c - a
即环前面的路程 = 数个环的长度(为可能为0) + c - a
什么是c - a?这是相遇点后,环后面部分的路程。(橙色路程)
所以,我们可以让一个指针从起点A开始走,让一个指针从相遇点B开始继续往后走,
2个指针速度一样,那么,当从原点的指针走到环入口点的时候(此时刚好走了x)
从相遇点开始走的那个指针也一定刚好到达环入口点。
所以2者会相遇,且恰好相遇在环的入口点。

最后,判断是否有环,且找环的算法复杂度为:

时间复杂度:O(n)

空间复杂度:O(1)
publicclassSolution {
 
    publicListNode EntryNodeOfLoop(ListNode pHead){
        ///
        if(pHead==null|| pHead.next==null|| pHead.next.next==null)returnnull;
        ListNode fast=pHead.next.next;
        ListNode slow=pHead.next;
        /////先判断有没有环
        while(fast!=slow){
            if(fast.next!=null&& fast.next.next!=null){
                fast=fast.next.next;
                slow=slow.next;
            }else{
                //没有环,返回
                returnnull;
            }
        }
        //循环出来的话就是有环,且此时fast==slow.
        fast=pHead;
        while(fast!=slow){
            fast=fast.next;
            slow=slow.next;
        }
        returnslow;
    }
}






下面的是断链法。不过题目要求不允许修改链表时就尴尬了。
publicclassSolution {
publicListNode EntryNodeOfLoop(ListNode pHead){
if(pHead==null|| pHead.next==null)returnnull;
ListNode fast=pHead.next;
ListNode slow=pHead;
while(fast!=null){
slow.next=null;
slow=fast;
fast=fast.next;
}
returnslow;
}
}


编辑于 2017-03-11 10:47:33 回复(53)
  1. 第一步,找环中相汇点。分别用p1,p2指向链表头部,p1每次走一步,p2每次走二步,直到p1==p2找到在环中的相汇点。
  2. 第二步,找环的入口。接上步,当p1==p2时,p2所经过节点数为2x,p1所经过节点数为x,设环中有n个节点,p2比p1多走一圈有2x=n+x; n=x;可以看出p1实际走了一个环的步数,再让p2指向链表头部,p1位置不变,p1,p2每次走一步直到p1==p2; 此时p1指向环的入口。

public class Solution {

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

发表于 2015-09-15 15:23:04 回复(60)


HashSet<ListNode> set = new HashSet<ListNode>();

while (pHead != null) {

if (!set.add(pHead)) {

return pHead;

}

pHead = pHead.next;

}

returnnull;

发表于 2015-10-07 12:45:55 回复(24)
/*
时间复杂度为O(n),两个指针,一个在前面,另一个紧邻着这个指针,在后面。
两个指针同时向前移动,每移动一次,前面的指针的next指向NULL。
也就是说:访问过的节点都断开,最后到达的那个节点一定是尾节点的下一个,
也就是循环的第一个。
这时候已经是第二次访问循环的第一节点了,第一次访问的时候我们已经让它指向了NULL,
所以到这结束。
*/
class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead)
    {
		if (!pHead->next)
			return NULL;
		ListNode* previous = pHead;
		ListNode* front = pHead ->next;
		while (front)
		{
			previous->next = NULL;
			previous = front;
			front = front->next;
		}
		return previous;
	}
};

编辑于 2016-01-26 16:36:01 回复(36)

两个结论:
1、设置快慢指针,假如有环,他们最后一定相遇。
2、两个指针分别从链表头和相遇点继续出发,每次走一步,最后一定相遇与环入口。
证明1:设置快慢指针fast和low,fast每次走两步,low每次走一步。假如有环,两者一定会相遇(因为low一旦进环,可看作fast在后面追赶low的过程,每次两者都接近一步,最后一定能追上)。
证明2:
设:
链表头到环入口长度为--a
环入口到相遇点长度为--b
相遇点到环入口长度为--c

则:相遇时
快指针路程=a+(b+c)k+b ,k>=1  其中b+c为环的长度,k为绕环的圈数(k>=1,即最少一圈,不能是0圈,不然和慢指针走的一样长,矛盾)。
慢指针路程=a+b
快指针走的路程是慢指针的两倍,所以:
(a+b)*2=a+(b+c)k+b
化简可得:
a=(k-1)(b+c)+c 这个式子的意思是: 链表头到环入口的距离=相遇点到环入口的距离+(k-1)圈环长度。其中k>=1,所以k-1>=0圈。所以两个指针分别从链表头和相遇点出发,最后一定相遇于环入口。
class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead)
    {
        ListNode*fast=pHead,*low=pHead;
        while(fast&&fast->next){
            fast=fast->next->next;
            low=low->next;
            if(fast==low)
                break;
        }
        if(!fast||!fast->next)return NULL;
        low=pHead;//low从链表头出发
        while(fast!=low){//fast从相遇点出发
            fast=fast->next;
            low=low->next;
        }
        return low;
    }
};

编辑于 2018-06-15 11:35:32 回复(2)
//左神讲的
//先说个定理:两个指针一个fast、一个slow同时从一个链表的头部出发
//fast一次走2步,slow一次走一步,如果该链表有环,两个指针必然在环内相遇
//此时只需要把其中的一个指针重新指向链表头部,另一个不变(还在环内),
//这次两个指针一次走一步,相遇的地方就是入口节点。
//这个定理可以自己去网上看看证明。
public class Solution {
    public ListNode EntryNodeOfLoop(ListNode pHead){
        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;
    }
}

发表于 2017-08-17 11:29:22 回复(12)
思路:leetcode上也有这道题,具体思想是,两个指针fast和slow,fast以slow两倍速度前进,
如果没有环,那么fast和slow不会相遇此时返回null;如果有环,那fast和slow肯定会再次相遇
相遇的时候,fast刚好比slow多走了一圈环的长度。  用图来描述下,当fast与slow相遇时,fast走过的距离为a + b + c + b,而slow走过的距离为
a + b,因为fast是slow速度的两倍,则有a+b+c+b = 2*(a+b),登出a=c;此时slow节点所处X处
到环起点Y处的距离a和X节点到Y处距离c其实是相等的,此时第三个指针p从x处,以和slow指针
相同的速度前进,当它两相遇时,即为环的起点Y处!

public class Solution {

    public ListNode EntryNodeOfLoop(ListNode pHead)
    {
        ListNode fast = pHead;
        ListNode slow = pHead;
        while(fast !=null && fast.next !=null) {
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow) {
                ListNode p = pHead;
                while( p != slow) {
                    p = p.next;
                    slow = slow.next;
                }
                return p;
            }
        }
        return null;
    }
}

编辑于 2017-05-18 13:02:17 回复(9)
class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead)
    {
        set<ListNode*> s;
       	ListNode* node = pHead;
        while(node!=NULL){
            if(s.insert(node).second)
                node = node->next;
            else
                return node;
        }
        return node;
        
    }
};
我这里用到了STL中的set,set有一个特性就是不能插入相同元素,这样只需遍历原List一次就可以判断出有没有环,还有环的入口地址。s.insert(node).second这里在插入的同时也判断了插入是否成功,如果不成功表明set中已经有该元素了,该元素就是环的入口元素。
发表于 2016-07-23 18:20:48 回复(5)

python solution:

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def EntryNodeOfLoop(self, pHead):
        # write code here
        slow,fast=pHead,pHead
        while fast and fast.next:
            slow=slow.next
            fast=fast.next.next
            if slow==fast:
                slow2=pHead
                while slow!=slow2:
                    slow=slow.next
                    slow2=slow2.next
                return slow
发表于 2017-10-07 19:25:27 回复(8)
要寻找环的入口节点,遍历节点的时候,遇到的第一个重复节点肯定入环节点,所以定义一个Set,
添加失败时  即返回入口节点
import java.util.*;
public class Solution {

    public ListNode EntryNodeOfLoop(ListNode pHead)
    {
        if(pHead==null)
            return null;
        ListNode pNode=pHead;
        HashSet<ListNode> pSet = new HashSet<ListNode>();
        while(pNode!=null){
            if(!pSet.add(pNode))
                return pNode;
            pNode=pNode.next;
        }
        return null;
    }
}

发表于 2016-06-18 10:34:08 回复(5)
'''
解法:
第一步,先找到环中的一个节点(找到之后就可以计算出环中的节点数目)
    让一个指针fast走快一点,一个指针slow走慢一点;当fast与slow相遇时,即fast比slow多一圈,此时相遇的节点肯定是环内的节点
第二步,根据环中的节点来计算环中节点总数
    从此节点遍历到此节点结束,即可得到节点总数
第三步,知道了环内节点总数,来找到环入口
    先让一个指针p1从根节点开始往后走m步,然后再让一个节点p2指向头结点;
    然后让p1和p2同时往后移动,当p1与p2相交时,此时的点就是环的入口节点
'''
class Solution:
    def EntryNodeOfLoop(self, pHead):
        # write code here
        meet_node = self.MeetNode(pHead)
        if meet_node == None:
            return None
        # 得到环中的节点个数
        loop_nodes = 1
        p1 = meet_node
        while p1.next != meet_node:
            loop_nodes += 1
            p1 = p1.next
        # 目前已经得到了环中节点个数m,和环中个一个节点meetnode,如何找到环的入口?
        # 一个指针p1从根节点开始往后走m步,然后再让一个节点p2指向头结点,p1和p2同时往后移动,当p1与p2相交时,此时的点就是环的入口节点
        p1 = pHead
        for i in range(loop_nodes):
            p1 = p1.next
        p2 = pHead
        while p1 != p2:
            p1 = p1.next
            p2 = p2.next
        return p1

    def MeetNode(self, pHead):
        if pHead == None:
            return None
        slow = pHead.next
        if slow == None:
            return None
        fast = slow.next
        while slow != None and fast != None:
            if slow == fast:
                return slow
            slow = slow.next
            fast = fast.next
            if slow != fast:
                fast = fast.next
        return None

编辑于 2018-05-19 14:52:05 回复(0)
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 = fast.next.next;
			slow = slow.next;
			if(fast == slow) break;
		}
		fast = pHead;
		while (fast != slow) {
			fast = fast.next;
			slow = slow.next;
		}
		return slow;
	}
}

发表于 2017-04-26 15:38:04 回复(0)

先贴代码,再解释;

public ListNode EntryNodeOfLoop(ListNode pHead)
      {
        if (pHead == null || pHead.next == null)
            return null;
        //step1 发现环
        ListNode walk = pHead, run = pHead;
        do {
            walk = walk.next;
            run = run.next.next;
        } while (walk != run);
        //step2 找到了环,并且run正在环内
        //另起一个quickWalk从pHead开始走,quickWalk和run再次相遇的地点就是环的入口
        ListNode quickWalk = pHead;
        while (quickWalk != run) {
            run = run.next.next;
            quickWalk = quickWalk.next.next;
        }
        return quickWalk;
    }
}
  • 第一步发现环,并找到了walk指针和run指针相遇的地点
  • 第二步另起一个quickWalk指针,和run指针保持同步,俩指针相遇点即为入口;

解释:

如图,每个距离的含义:

  • S:环入口到walk和run相遇点的距离
  • L:walk和run相遇点到入口的距离
  • P:头结点到环入口的距离

设walk的速度是v,则run的速度是2v;

设相遇花费了t时间,walk走过的路程为Swalk

根据题意有: 2vt - vt = vt

又相遇的时候:vt = k(S+L)--①成立;

Swalk = vt = P + m(S+L) + S--②成立;

①②可得 k(S+L) = P + m(S+L) + S

变形为:P = (k-m-1)(S+L) + L

q = (k-m-1),最终得到 P = q(S+L) + L

因此分别从相遇地点、头结点同时以相同的速度走的俩指针,最终相遇地点一定是环的入口。


PS:最后两个同步指针的速度应该是越快越好,因此,采用另起一个quickWalk指针和run同步,而不是和walk同步。

编辑于 2017-12-18 15:45:35 回复(1)
//时间复杂度:O(n),用map对访问过的节点做标记,这样如果访问一个节点两次,表明找到了环入口,否则没有环。 表示map好好用啊~~
class EntryNodeOfLoop
{
public:
    ListNode* EntryNodeOfLoop_Solution(ListNode* pHead)
    {
        if(pHead==nullptr) return nullptr;
        ListNode *ptmp=pHead;
        map<ListNode*,int> mlist; //用map关联各个链表指针和对应的映射值
        while(ptmp!=nullptr && mlist[ptmp]!=1)
        {
            mlist[ptmp]=1;//访问过该链表节点,就将实值改为1
            ptmp=ptmp->next;
        }
        if(ptmp==nullptr) return nullptr; //没有环
        else return ptmp; //入口节点
    }
};

发表于 2017-05-22 22:29:30 回复(3)
剑指offer 上面提到了一种很巧妙的方法:
1. 知道环的长度 len
2. 让一个结点先走 len 然后让另一个 和先走的那个一起走,两者必然会相遇。
问题归结为,计算len.
整体流程:
1. 用快慢指针求相遇的结点(如果不存在相遇的结点,返回null 不用后面的计算)
2.  求len
3. 求入口节点。

我们这里使用HashMap , 效率比 ArrayList 效率高点。
/*
 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){
        ListNode node = pHead;
        
        HashMap<ListNode,Boolean> map = new HashMap<>();
        
        while(node!=null){
            if(map.containsKey(node)){
                return node;
            }else{
                map.put(node,true);
                node = node.next;
            }
        }
        
        return null;
    }
}

发表于 2016-06-01 16:31:14 回复(2)
class Solution:
    def EntryNodeOfLoop(self, pHead):
        # write code here
        linkls = []
        while pHead:
            if pHead in linkls:
                return pHead
            linkls.append(pHead)
            pHead = pHead.next
        return None

发表于 2018-07-05 19:59:29 回复(4)
package entryNodeOfLoop;

import java.util.HashSet;

public class Solution {

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

发表于 2018-03-10 21:29:48 回复(0)
//快慢指针。题目中明明说了有环。可是为何还要判断下?
class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead)
    {
        ListNode *slow = pHead; 
        ListNode *fast = pHead;
       	do{
            if(fast == NULL || fast->next==NULL)
                return NULL;
            fast = fast->next->next;
            slow = slow->next;    
        }while(slow != fast);
        slow = pHead;
        while(slow != fast){
            slow = slow->next;
            fast = fast->next;
        }
        return slow;    
    }
};

发表于 2017-06-07 14:48:40 回复(4)
List<ListNode> list = new ArrayList<ListNode>();
		while(!list.contains(pHead))
		{
			list.add(pHead);
			if(pHead.next!=null)
				pHead = pHead.next;
			else
				break;
		}
		if(pHead.next == null)return null;
		return pHead;

发表于 2016-09-01 10:45:24 回复(0)
//先快慢指针,相遇后将其中一个指针指向pHead 然后一起走,每次往后挪一位,相遇的节点就是所求
/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead)
    {
       ListNode *fast=pHead;
       ListNode *slow=pHead;
       if(slow && slow->next){
           slow=slow->next;
       }
       else{
           return NULL;
       }
        if(fast && fast->next && fast->next->next){
           fast=fast->next->next;
        }
        else{
            return NULL;
        }
        while(fast!=slow){
           if(slow==NULL || slow->next==NULL || fast==NULL || fast->next==NULL || fast->next->next==NULL){
               return NULL;
           }
           fast=fast->next->next;
           slow=slow->next;
       } 
        
        slow=pHead;
        while(fast!=slow){
           fast=fast->next;
           slow=slow->next;
        }
        return fast;
    }
};

发表于 2016-08-31 15:26:23 回复(2)