首页 > 试题广场 >

链表中环的入口结点

[编程题]链表中环的入口结点
  • 热度指数：668838 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给一个长度为n链表，若其中包含环，请找出该链表的环的入口结点，否则，返回null。

数据范围： ，
要求：空间复杂度 ，时间复杂度

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

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

输入描述:
输入分为2段，第一段是入环前的链表部分，第二段是链表环的部分，后台会根据第二段是否为空将这两段组装成一个无环或者有环单链表


输出描述:
返回链表的环的入口结点即可，我们后台程序会打印这个结点对应的结点值；若没有，则返回对应编程语言的空结点即可。
示例1

输入

{1,2},{3,4,5}

输出

3

说明

返回环形链表入口结点，我们后台程序会打印该环形链表入口结点对应的结点值，即3
示例2

输入

{1},{}

输出

"null"

说明

没有环，返回对应编程语言的空结点，后台程序会打印"null"
示例3

输入

{},{2}

输出

2

说明

环的部分只有一个结点，所以返回该环形链表入口结点，后台程序打印该结点对应的结点值，即2

说明：本题目包含复杂数据结构ListNode，点此查看相关信息
算法知识视频讲解
添加回答
推荐
Top_bo头像 Top_bo
如果链表中环 有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 回复(45)
Java
却顾所来径头像 却顾所来径

思路：

    设置快慢指针，都从链表头出发，快指针每次走两步，慢指针一次走一步，假如有环，一定相遇于环中某点(结论1)。接着让两个指针分别从相遇点和链表头出发，两者都改为每次走一步，最终相遇于环入口(结论2)。以下是两个结论证明：

两个结论：

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圈。所以两个指针分别从链表头和相遇点出发，最后一定相遇于环入口。 
C++版：

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;
    }
};

java版：

public class Solution {

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

编辑于 2019-12-04 12:29:55 回复(53)
0909头像 0909
  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 回复(66)
求一个大大的offer头像 求一个大大的offer
【转】 
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 回复(67)
Java
QAQWQAQ头像 QAQWQAQ 
    /**
        用Set判断重复
    **/
    public ListNode EntryNodeOfLoop(ListNode pHead) {
        HashSet<ListNode> set = new HashSet<>();
        while (pHead != null) {
            if(set.contains(pHead)){
                break;
            }
            set.add(pHead);
            pHead = pHead.next;
        }
        return pHead;
    }

发表于 2021-08-23 18:58:32 回复(1)
weizier头像 weizier 
        if(head==null) return null;
        ListNode fastNode = head;
        ListNode slowNode = head;
        while(true){
            if((fastNode.next!=null)&&(fastNode.next.next!=null)){
                fastNode = fastNode.next.next;
                slowNode = slowNode.next;
            }else return null;
            if(fastNode == slowNode) break;
        }
        fastNode = head;
        while(true){
            if(fastNode==slowNode) break;
            fastNode = fastNode.next;
            slowNode = slowNode.next;
        }
        return slowNode;

发表于 2015-06-14 01:20:45 回复(0)
C++
Spectre_头像 Spectre_ 
/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead) {
        // 时间复杂度O(N)，空间复杂度O(1)
        if (pHead == nullptr) return nullptr;
        ListNode *slow = pHead, *fast = pHead;
        while (fast->next && fast->next->next) {
            slow = slow->next;
            fast = fast->next->next;
            if (fast == slow) {
                fast = pHead;
                while (fast != slow) {
                    fast = fast->next;
                    slow = slow->next;
                }
                return fast;
            }
        }
        return nullptr;
    }
};

发表于 2022-08-18 22:20:36 回复(0)
C++
愉快的大白菜不讲武德头像 愉快的大白菜不讲武德
利用 题目的 对 val 的限制 , 1<=val<=10000;  每遍历一个 节点, val 值+ 10000;  当遍历到 节点的val 值> 10000, 此节点为入口点. 
若遍历到 nullptr, 无入口点. 
ListNode *EntryNodeOfLoop(ListNode *pHead) {
    while (pHead) {
        if (pHead->val > 10000) {
            pHead->val = pHead->val - 10000;
            return pHead;
        }
        pHead->val = pHead->val + 10000;
        pHead = pHead->next;
        if (pHead == nullptr) return nullptr;
    }
    return nullptr;
}



发表于 2022-08-07 03:05:35 回复(0)
菜团子鼠鼠头像 菜团子鼠鼠 
struct ListNode* EntryNodeOfLoop(struct ListNode* pHead ) {
    struct ListNode*p = pHead;
    struct ListNode*q = pHead;
    if(pHead == NULL)
    {
        printf("null");
        return NULL;
    }
    while(p != NULL&&p->next!=NULL)
    {
        p = p->next->next;//快慢指针判断是否有环，p走两步，q走一步
        q = q->next;
        if(q == p)//相遇证明有环,并且记录这个结点
        {
            p = pHead;//一个结点回到头结点，另外一个留在相遇的位置
            while(p!=NULL && p->next!=NULL)
            {
                if(q == p)//当p与q相遇时，这个地方就是循环结点入口！
                {
                    printf("%d",p->val);
                    return p;
                }
                p = p->next;//p,q都一步一步走
                q = q->next;
            }
        }
    }
    printf("null");
    return NULL;
}

发表于 2022-07-22 20:18:53 回复(0)
C++
哆啦k梦头像 哆啦k梦 
/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution{
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead)
    {
        set<ListNode*> s;
        while(pHead!=NULL)
        {
            if(s.find(pHead)!=s.end())
                return pHead;
            s.insert(pHead);
            pHead=pHead->next;
        }
        return pHead;
    }
};

发表于 2022-07-20 16:11:50 回复(0)
Java
暴风陨石坠头像 暴风陨石坠 
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;
            }
            slow = pHead;
            while (fast != slow){
                fast = fast.next;
                slow = slow.next;
            }
            return slow;
    }
}

发表于 2022-05-08 23:23:29 回复(0)
Java
牛客536818025号头像 牛客536818025号
日常投机取巧 
public class Solution {
    public ListNode EntryNodeOfLoop(ListNode pHead) {
        while(pHead!=null){
            if(pHead.val>10000){
                pHead.val-=10000;
                return pHead;
            }
            else{
                pHead.val+=10000;
                pHead=pHead.next;
            }
        }
        return null;
    }
}


发表于 2022-03-16 18:54:08 回复(0)
Java
得意萝菠头像 得意萝菠
看到找环 想到快慢指针，看到找环入口第一感觉是快慢指针不太适用，要是有个flag标识就好了，那样若是最早遍历第二遍的结点就是入口节点。发现题目所给结点值均大于0，因此想到了遍历时将结点值取负作为标识，最终返回时再取负复原。
提供 一种垃圾快速解法。 
public class Solution {

    public ListNode EntryNodeOfLoop(ListNode pHead) {
       /*
       ListNode s=pHead,q=pHead;//常规快慢指针
        while(s!=null&&q!=null){
            s=s.next;
            if(q.next==null) return null;
            q=q.next.next;
            if(s==q)
            {
                ListNode p=pHead;
                while(p!=s){
                    p=p.next;
                    s=s.next;
                }
                return p;
            }
        }
        if(q!=s) return null;
        return s;
        */
        
        while(pHead!=null){    //垃圾快速解法 只适用特定条件
            if(pHead.val<0){
                pHead.val=-pHead.val;
                 return pHead;
            }
            pHead.val=-pHead.val;
            pHead=pHead.next;
        }
        return null;
    }
}


发表于 2022-03-12 17:33:51 回复(0)
Java
JayChou1999头像 JayChou1999 
/*
 public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
*/
import java.util.*;
public class Solution {
    public ListNode EntryNodeOfLoop(ListNode pHead) {
        Set set = new HashSet<Integer>();//声明集合存放节点循环的值
        ListNode res = null;
        if(pHead.next == null)return null;
        
        while(pHead != null){
            if(set.add(pHead.val)){//如果存在重复的元素就是需要找的公共节点，此时就可以返回该对象
                pHead = pHead.next;
            }else
                break;
        }
        return pHead;
    }
}

发表于 2022-03-04 17:47:17 回复(0)
牛客841422626号头像 牛客841422626号
其实我就很不懂了，不是说好两个输入的吗，怎么就原始代码给一个形参传入？？
发表于 2022-02-09 22:03:06 回复(0)
Java
thai头像 thai
因为 val 值最大为 10000，可以给访问过的结点做个标记，加上 10001，下次再遇到大雨等于 10001 值的就是环入口了。 
public ListNode EntryNodeOfLoop(ListNode pHead) {
    int num = 10001;
    ListNode p = pHead;
    while (p != null) {
        if (p.val >= num) {
            p.val = p.val - num;
            return p;
        }
        p.val = p.val + num;
        p = p.next;
    }
    return null;
}


发表于 2022-01-29 21:41:20 回复(0)
牛客275043970号头像 牛客275043970号
借用一下楼上的图，看了很多其他的方法还是没怎么看懂，写一下自己的解法
1.首先我们有两个指针，一个fast指针，每次移动两步，一个slow指针，每次移动一步
2.在有环的情况下，两个指针必然相遇，设相遇的时候 慢指针走了 j 步 即 slow = j ， n 为环的长度
这个时候快指针肯定是要比慢指针走多了几个环才能和慢指针相遇（具体也不清楚），
不过我们可以得到的是    fast= j + i*n
3. 然后我们之前设置了两个指针的移动速度，所以我们可以得到  fast = 2 * slow = 2j
由于 ， fast = j+i*n  所以，j = i*n 

4. 在（3）中我们就可以明确的得到，第一次相遇时，指针走过的路径（从链表头开始）必然是环的倍数
就可以得到  a+b + kn = i*n  =>  a+b = (i-k)n  这个圈数(i-k)不重要，我们只用知道他是一个大于等于1的数即可 
简化点写就是  a+b = m*n (m>=1)

5. 因为  b + c = n  所以 a+b = m*n  =>  a= (m-1)*n + c(m >=1) , 
这一步我们就可以得到 =》 a 的长度 = 环长度倍数 + c 
在第一次相遇点到环节点剩下的长度为 => slow剩余长度 = 环长 - b = c 

6. 所以最重要的一步在这里，此时如果有一个指针 new 从链表头开始 和 slow 指针相同速度并且同时出发，
会发生什么？
我们先分析 new指针，该指针经过a的长度相当于（5）的  a的长度 =  环长度倍数 + c ，重点在这，把他拆成两部看，并且观察slow指针此时的位置
即：第一步：经过环长度倍数（可以是0可以是其他倍数，无所谓），这个时候 slow指针 肯定还是在原来的位置（经过了环长的倍数嘛）
       第二步：在第一步过后  new指针到环节点剩余的路程为 c ；指针 slow还在原来的地方，距离环节点的路程不就是c吗，
       第三步：由第二步我们就知道，new指针和slow指针必定在环节点处相遇，代码就不贴了，相信各位看懂的话肯定可以理解，写的太乱望体谅



发表于 2022-01-13 16:53:12 回复(0)
C++
tinyChai头像 tinyChai 
class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead) {
        if (pHead==nullptr)
            return pHead;
        map<int, int> p;
        int i=0;
        while(!p.count(pHead->val) && pHead->next!=nullptr)
        {
            p.insert(pair<int, int>(i,pHead->val));
            i++;
            pHead=pHead->next;
        }
        if(pHead->next==nullptr)
            return nullptr;
        return pHead;
    }
};

发表于 2021-12-24 16:56:59 回复(0)
Go
nn_123头像 nn_123
package main

func EntryNodeOfLoop(pHead *ListNode) *ListNode{
    var hMap = make(map[*ListNode]int, 0)
    for {
        if pHead == nil {
            return pHead
        }
        if _,ok := hMap[pHead]; ok {
            return pHead
        }
        hMap[pHead] = 1
        pHead = pHead.Next
    }
}
发表于 2021-11-22 14:09:15 回复(0)
Javascript
♈FourBrother✅已认证♉头像 ♈FourBrother✅已认证♉
我觉得可以用map解决 
function EntryNodeOfLoop(pHead)
{
    // write code here
    if (pHead.next === null) return null
    const map = new Map()
    let currentNode = pHead
    while(currentNode) {
        if (map.has(currentNode)) return currentNode
        else map.set(currentNode, currentNode)
        currentNode = currentNode.next
    }
    return null
}


发表于 2021-11-18 09:47:45 回复(0)
Java
亨利护球像我头像 亨利护球像我
利用set的特性，遍历链表，如果存在环，第一个无法插入的节点就是入口节点 

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

发表于 2021-11-13 18:24:22 回复(0)
提交观点

问题信息

链表 哈希 双指针
难度：
1477条回答 131495浏览

热门推荐

通过挑战的用户

查看代码

相关试题

链表中环的入口结点

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号