首页 > 试题广场 >

链表中环的入口结点

[编程题]链表中环的入口结点
  • 热度指数：645937 时间限制：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
牛客139020153号头像 牛客139020153号
难绷，快慢指针我只会上一题简单版，这题完全瞎碰 
public ListNode EntryNodeOfLoop(ListNode pHead) {
      HashMap<Integer,Integer> map=new  HashMap<Integer,Integer>();
      int i=0;
            while(pHead!=null){
                i++;
                       if( map.put(pHead.hashCode(),i)!=null){
                        return pHead;
                       }
                       pHead=pHead.next;
            }
            return null;
       
    }
编辑于 2024-04-05 01:47:21 回复(0)
Java
牛客119190309号头像 牛客119190309号
 public ListNode EntryNodeOfLoop(ListNode pHead) {
        Integer num = null;
        HashMap<Integer,Integer> map = new HashMap<>();
        while (pHead != null ) {
            if (map.containsKey(pHead.val)) {
                num = pHead.val;
                break;
            } else {
                map.put(pHead.val, 1);
            }
            pHead = pHead.next;
        }
        if (num == null) {
            return null;
        }
        ListNode node = new ListNode(num);
        return node;
    }
编辑于 2024-02-28 22:03:16 回复(0)
Java
牛客608726307号头像 牛客608726307号 
public class Solution {

    //链表头到环入口的距离=相遇点到环入口的距离+（k-1）圈环长度
    //判断有没有环，返回相遇的地方
    public ListNode hasCycle(ListNode head) {
        //先判断链表为空的情况
        if (head == null)
            return null;
        //快慢双指针
        ListNode fast = head;
        ListNode slow = head;
        //如果没环快指针会先到链表尾
        while (fast != null && fast.next != null) {
            //快指针移动两步
            fast = fast.next.next;
            //慢指针移动一步
            slow = slow.next;
            //相遇则有环，返回相遇的位置 
            if (fast == slow)
                return slow;
        }
        //到末尾说明没有环，返回null
        return null;
    }

    public ListNode EntryNodeOfLoop(ListNode pHead) {
        ListNode slow = hasCycle(pHead);
        //没有环
        if (slow == null)
            return null;
        //快指针回到表头
        ListNode fast = pHead;
        //再次相遇即是环入口
        while (fast != slow) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
}

发表于 2024-02-20 21:54:08 回复(0)
Java
认真求职的熊二头像 认真求职的熊二 
import java.util.*;
/*
 public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {

    public ListNode EntryNodeOfLoop(ListNode pHead) {
        //如果没有节点或者只有一个节点，就不可能有环入口，直接返回null
        if (pHead == null || pHead.next == null){
            return null;
        }
        //我定义了一个快指针，一个慢指针，快指针每次跑两个节点，慢指针每次跑一个节点
        ListNode fast = pHead;
        ListNode low = pHead;
        while (fast.next != null && fast.next.next != null){
            low = low.next;
            fast = fast.next.next;
            if (low == fast){ //说明有环路
                low = pHead; //让慢指针重新指向头节点，这次快慢指针每次都跑一个节点
                while(low != fast){
                    low = low.next;
                    fast = fast.next;
                }
                 return low;
            }
        }
        //如果能走到这里，就说明没有环路，也返回null
        return null;
    }
}


发表于 2023-11-26 23:51:52 回复(0)
Java
甲乙丙丁201901162305707头像 甲乙丙丁201901162305707
笔试遇到的题，四十分钟没做出来，回来趟床上突然想到这个方法。拍断大腿。
因为测试集全是正数，直接将走过的点置为相反数就行了 
import java.util.*;
/*
 public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {

    public ListNode EntryNodeOfLoop(ListNode pHead) {
        while(pHead != null && pHead.val > 0){
            pHead.val = -pHead.val;
            pHead = pHead.next;
        }
        if(pHead == null){
            return null;
        }else{
            pHead.val = -pHead.val;
            return pHead;
        }
    }
}


发表于 2023-11-24 21:17:44 回复(1)
Java
牛客336749033号头像 牛客336749033号
快慢指针
假设 从起点到环入口长度为a，环长度为b，相遇点为k，
那么 a+n圈的b，都能找到入口
快指针走的距离：a + nb + k
慢指针走的距离：a + mb +k
快指针速度是慢指针的2倍，相减，慢指针 = 快指针-慢指针 = （相差的n圈）* b
因为a+nb都能找到入口，则再走a步就可以了，让慢指针会到原点，再走a长度就是环入口
发表于 2023-10-25 15:15:03 回复(0)
Java
飀头像 飀 
import java.util.*;
/*
 public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {

    public ListNode EntryNodeOfLoop(ListNode pHead) {
        
        while(pHead != null){
            if(pHead.val < 0){
                pHead.val = pHead.val + Integer.MAX_VALUE;
                return pHead; 
            }else{
                pHead.val = pHead.val - Integer.MAX_VALUE;
                pHead = pHead.next;
            }
        }
        return null;

    }
}

思路：走过更新数据为负数，当值为负数表示有环，把数还原回来，在这里使用了int最大值

发表于 2023-10-11 23:33:36 回复(2)
Java
王总统治世界头像 王总统治世界
这个和上个判断是否有环的题没什么区别 
public class Solution {

    public ListNode EntryNodeOfLoop(ListNode pHead) {
        HashSet<ListNode> hasCycleSet = new HashSet<>();
       
        while(pHead != null){
            if(hasCycleSet.contains(pHead)){
                // 下一个节点已记录
                return pHead;
            }else{
                // 下一个节点未记录
                hasCycleSet.add(pHead);
            }
            pHead = pHead.next;
        }
        return null;
    }
}


发表于 2023-09-26 02:10:24 回复(0)
Java
LQY_头像 LQY_ 

public ListNode EntryNodeOfLoop(ListNode pHead) {
    	HashSet<ListNode> list = new HashSet<>();
    	while(!list.contains(pHead) && pHead != null) {
    		list.add(pHead);
    		pHead = pHead.next;
    	}
    	return pHead;
    }

发表于 2023-09-17 19:17:19 回复(0)
Java
dqxfz头像 dqxfz
public class Solution {

    public ListNode EntryNodeOfLoop(ListNode pHead) {
        while(pHead != null) {
            if (pHead.val < 0) {
                // 如果小于0表示已经遍历过这个节点了，变成正数后返回
                pHead.val = -1 * pHead.val;
                return pHead;
            }
            // 取负数表示遍历过这个节点
            pHead.val = -1 * pHead.val;
            pHead = pHead.next;
        }
        return null;
    }
}
发表于 2023-09-08 14:36:28 回复(0)
Java
大白熊_plus头像 大白熊_plus 
public class Solution {
    public ListNode EntryNodeOfLoop(ListNode pHead) {
        List<ListNode> isTo = new ArrayList<>();
        while (pHead != null) {
            if (isTo.contains(pHead)) {
                return pHead;
            } else {
                isTo.add(pHead);
                pHead = pHead.next;
            }
        }
        return null;
    }
}

发表于 2023-09-07 17:20:01 回复(0)
Java
@唯时头像 @唯时 
public class Solution {
    public ListNode EntryNodeOfLoop(ListNode pHead) {
        ListNode slow = pHead;
        ListNode fast = pHead;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                ListNode index1 = slow;
                ListNode index2 = pHead;
                while (index1 != index2) {
                    index1 = index1.next;
                    index2 = index2.next;
                }
                return index2;
            }
        }
        return null;
    }
}

发表于 2023-09-06 17:29:27 回复(0)
Java
望三星头像 望三星
分享一个暴力解法：从头结点开始删除（next 置空），直到剩余链表成环的条件被破坏 
public ListNode EntryNodeOfLoop(ListNode pHead) {
    if (pHead == null || !isLoop2(pHead)) return null;
    if (pHead.next == pHead) return pHead;
    ListNode prior = pHead;
    ListNode cur = pHead.next;
    while (isLoop2(prior)) {
        prior.next = null;
        prior = cur;
        cur = cur.next;
    }
    while (cur.next != null) {
        cur = cur.next;
    }
    return cur;
}

public boolean isLoop1(ListNode head) {
    int count = 0;
    while (count < 10001 && head != null) {
        count++;
        head = head.next;
    }
    return count == 10001;
}

public boolean isLoop2(ListNode head) {
    ListNode slow = head;
    ListNode fast = head;
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;
        if (slow == fast) {
            return true;
        }
    }
    return false;
}
剩余链表成环的条件被破坏后，cur 或 prior 的最终next 一定是入口节点

时间复杂度：，空间复杂度：O(1)。
isLoop1()是根据题干要求10000个数，则循环超过10000则必存在环；
isLoop2()是根据快慢指针启发写的判断存在环的方法。

发表于 2023-09-02 11:02:36 回复(0)
Java
牛客101757813号头像 牛客101757813号 
public ListNode EntryNodeOfLoop(ListNode pHead) {
        if(pHead == null || pHead.next == null){
            return null;
        }
        List<ListNode> list = new ArrayList<>();
        while(pHead != null){
            if(list.contains(pHead)){
                //如果包含，说明已经出现环了，且入口就是它
                return pHead;
            }
            list.add(pHead);
            pHead = pHead.next;
        }
        return null;
    }

发表于 2023-08-03 11:01:31 回复(0)
Java
做则必成的勇气和信心头像 做则必成的勇气和信心 
public ListNode EntryNodeOfLoop(ListNode pHead) {
        //只有一个链
        ListNode fast=pHead;
        ListNode slow=pHead;
        while(fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
            while(fast==slow){
                ListNode index1=fast;//一个从fast走，一个从pHead走
                ListNode index2=pHead;
                while(index1!=index2){
                    index1=index1.next;
                    index2=index2.next;
                    
                }
                return index1;//如果找到环的入口，就return index1
            }
        }
        return null;//如果没有找到return null   
    }

发表于 2023-07-17 19:43:56 回复(0)
Java
抓住努力的尾巴头像 抓住努力的尾巴 
import java.util.*;
/*
 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 || pHead.next == 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;
        }
        slow = pHead;

        while (fast != slow) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
}
发表于 2023-07-10 12:40:12 回复(0)
Java
爱吃大白菜⁣⁣⁣⁣头像 爱吃大白菜⁣⁣⁣⁣
使用set，遍历链表；如果set中没有这个节点，就存入这个节点，如果有这个节点，这个节点就是入口节点 
import java.util.*;
/*
 public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {

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


发表于 2023-06-25 18:26:14 回复(0)
提交观点

问题信息

链表 哈希 双指针
难度：
282条回答 129884浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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