首页 > 试题广场 >

链表中环的入口结点

[编程题]链表中环的入口结点
  • 热度指数：645105 时间限制：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)
Python
牛客834091834号头像 牛客834091834号 
class Solution:
    def EntryNodeOfLoop(self, pHead):
        vessel = set()
        
        while pHead:
            if pHead in vessel:
                return pHead 
            else:
                vessel.add(pHead)
                pHead = pHead.next
        return pHead
习惯用数组，数组太慢过不了，改成集合
发表于 2022-09-13 19:47:32 回复(0)
Python
Hiroi头像 Hiroi
Python 如果长度0或1，或有none，则无环。如果有环，快慢指针追上的时候断开，变成有公共节点的两个链表，再去找公共节点。有一点不明白的是：为什么如果以追上的时候的快慢指针为头节点，两个链表长度会是一样的？ 
# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def getListLen(self,head):
        pos=head
        n=0
        while pos is not None:
            n+=1
            pos=pos.next
        return n
    def EntryNodeOfLoop(self, pHead):
        # write code here
        if pHead is None&nbs***bsp;pHead.next is None:
            return None
            
        slow = pHead
        fast = pHead
        while slow.next and fast.next.next:
#             temp = slow
            slow = slow.next
            fast = fast.next.next
            if slow is fast:
                nHead = slow.next
#                 temp.next = None # 断开
                slow.next = None
                len1 = self.getListLen(pHead)
                len2 = self.getListLen(nHead)
                if len1>len2:
                    for i in range(len1-len2):
                        pHead=pHead.next
                else:
                    for i in range(len2-len1):
                        nHead=nHead.next
                while True:
                    if pHead is nHead:
                        return pHead
                    pHead=pHead.next
                    nHead=nHead.next
        return None


发表于 2021-04-18 02:32:54 回复(0)
Python
牛客541273514号头像 牛客541273514号 
# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def EntryNodeOfLoop(self, pHead):
        # write code here
        if pHead is None:
            return None
        p1=pHead
        p2=pHead
        ##确定是否有环
        num=0
        while p2.next and p2.next.next and num==0:
            p2=p2.next.next
            p1=p1.next
            if p1.val==p2.val:
                p=p1
                num+=1
        if num==0:
            return None
        ##确定环的节点数n
        p=p.next
        n=1
        while p.val!=p1.val:
            n+=1
            p=p.next
        p3=pHead
        p4=pHead
        for i in range(n):
            p3=p3.next
        while p3.val !=p4.val:
            p3=p3.next
            p4=p4.next
        return p3
跟着剑指一步一步走
发表于 2021-04-16 00:10:53 回复(0)
Python
在下小6头像 在下小6

python解法：
解法1:哈希表；

class Solution:
    def EntryNodeOfLoop(self, pHead):
        hash = {}
        while pHead:
            if pHead not in hash:
                hash[pHead] = 1
            else:
                return pHead
            pHead = pHead.next
        return None

解法2:快慢指针，妙啊～
快指针一次走两步，满指针一次走一步，相遇后停止；
之后再用一个指针从头出发，同时慢指针再继续走，两者相遇的地方即环入口；
具体讲解见图：
图片说明 

class Solution:
    def EntryNodeOfLoop(self, pHead):
        slow, fast = pHead, pHead
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
            if slow == fast:
                break
        if not fast or not fast.next:
            return None
        p = pHead
        while p != slow:
            p = p.next
            slow = slow.next
        return p
发表于 2021-02-23 20:27:17 回复(0)
Python
字节校招内推官头像 字节校招内推官 
# -*- 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 fast == slow:
                slow = pHead
                while slow!=fast:
                    slow = slow.next
                    fast = fast.next
                return slow
发表于 2020-12-26 01:23:02 回复(0)
Python
老和山小学生头像 老和山小学生 
# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def EntryNodeOfLoop(self, pHead):
        # write code here
        # 确定是否有环
        if not pHead&nbs***bsp;not pHead.next:
            return None
        Node1 = pHead.next
        Node2 = pHead.next.next
        while Node1 != Node2:
            if Node1.next.next and Node2.next:
                Node1 = Node1.next.next
                Node2 = Node2.next
            else:
                return None
        # 确定环的长度
        TempNode = Node1.next
        LoopLength = 1
        while TempNode != Node1:
            TempNode = TempNode.next
            LoopLength += 1
        # 确定环的入口
        Node1 = pHead
        Node2 = pHead
        i = LoopLength
        while i:
            Node1 = Node1.next
            i -= 1
        while Node1 != Node2:
            Node1 = Node1.next
            Node2 = Node2.next
        return Node1

发表于 2020-10-10 21:06:40 回复(0)
Python
牛客820025436号头像 牛客820025436号 
class Solution:
    def EntryNodeOfLoop(self, pHead):
        # write code here
        if pHead == None:
            return None
        pTmp = pHead
        set1 = set()
        while pTmp:
            if pTmp in set1:
                return pTmp
            set1.add(pTmp)
            pTmp = pTmp.next
        return None

发表于 2020-09-10 17:32:30 回复(0)
Python
BJ-2020头像 BJ-2020

图片说明
借用楼上图说明一下
主要思路：
1.fast指针一次2个next,slow 一次一个next
2.确认有环：fast与slow重合
3.确定环节点：前面重合点继续slow到下一次又重合
4.初始位置相隔k个点，再一次相遇就是入口

其实也可以不用计算k
fast = slow + ring = 2*slow
slow = ring
因此上面直接可以进行第三步，直接让一个指针从头开始，当两个指针重回时，即为入口

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def EntryNodeOfLoop(self, pHead):
        # write code here
        if pHead == None:
            return None
        # 确认有环
        fast = pHead
        slow = pHead
        while fast:
            if fast.next:
                fast = fast.next.next
                slow = slow.next
            if not fast:
                return None
            if fast == slow:
                break
        # 找到环的节点数
        # 上面的相遇点一定是在环内，因此在环内循环一圈就能找到节点数
        k = 0
        while fast:
            fast = fast.next
            k += 1
            if fast == slow:
                break
        fast = pHead
        slow = pHead
        for i in range(k):
            fast = fast.next
        # 前后相隔k个点，同时相同速度，相交点就是入口
        while fast:
            if fast == slow:
                break
            fast = fast.next
            slow = slow.next
        return fast
发表于 2020-09-01 22:32:21 回复(0)
Python
yamx头像 yamx
python字典存储每一个经过的节点，如果某一个节点出现字典中，则说明该节点就是环的入口。 
class Solution:
    def EntryNodeOfLoop(self, pHead):
        # write code here
        dic = {}
        while pHead:
            if dic.get(pHead):
                return pHead
            else:
                dic[pHead] = True
            pHead = pHead.next
        return None


编辑于 2020-08-30 12:55:29 回复(0)
Python
DDooo头像 DDooo 
# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def EntryNodeOfLoop(self, pHead):
        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

相遇时
快指针路程=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圈。所以两个指针分别从链表头和相遇点出发，最后一定相遇于环入口。
发表于 2020-07-27 17:07:53 回复(0)
Python
刘嘉图头像 刘嘉图 
class Solution:
    def EntryNodeOfLoop(self, pHead):
        #如果链表为空
        if not pHead:
            return None
        #s保存遍历过的节点，s初始值为第一个节点
        s = {pHead}
        #从第二个节点开始遍历
        p = pHead.next
        #p不为空，为空说明没环
        while p:
            #如果p指向的节点不在集合s中,把p添加到s中，p接着指向下一个节点
            if p not in s:
                s.add(p)
                p = p.next
            #如果p指向的节点在集合s中，说明有环，且入口就是p
            else:
                return p
        return None   

发表于 2020-07-08 00:20:46 回复(0)
Python
生下来就会跑头像 生下来就会跑 
class Solution:
    def EntryNodeOfLoop(self, pHead):
        self.buffer = []
        return self.fun(pHead)
    def fun(self,pHead):
        if not pHead:return None
        if pHead.val in self.buffer:
            return pHead
        self.buffer.append(pHead.val)
        return self.fun(pHead.next)

发表于 2020-06-23 23:30:07 回复(0)
Python
一直爬的蜗牛头像 一直爬的蜗牛 
# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def EntryNodeOfLoop(self, pHead):
        # write code here
        tmp_list = []
        p = pHead
        while p:
            if p in tmp_list:
                return p
            else:
                tmp_list.append(p)
            p = p.next

发表于 2020-06-17 11:24:31 回复(0)
Python
ssssxt头像 ssssxt 
# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
        
    def EntryNodeOfLoop(self, pHead):
        # write code here
        visited = []
        while pHead:
            if pHead in visited:
                return pHead
            else:
                visited.append(pHead)
                pHead = pHead.next
        return None

发表于 2020-05-23 12:56:36 回复(0)
Python
努力学习的小贺头像 努力学习的小贺

思路 先判断是否存在环，再判断入口

class Solution:
def EntryNodeOfLoop(self, pHead):
# write code here
if pHead==None or pHead.next==None or pHead.next.next==None:
return None
slow=pHead
fast=pHead
while slow.next!=None and fast.next.next!=None:
slow=slow.next
fast=fast.next.next
if slow==fast:
isLinkedListContainsLoop=True
break
if isLinkedListContainsLoop:
slow=pHead
while slow!=fast:
slow=slow.next
fast=fast.next
return slow
return null

发表于 2020-03-31 18:19:03 回复(0)
Python
llfgo4it头像 llfgo4it 
class Solution:
    def EntryNodeOfLoop(self, pHead):
        # write code here
        # record the path
        if pHead == None:
            return None
        sy = []
        p = pHead
        while p != None:
            for i in sy:
                if i == p.next:
                    return i
            sy.append(p)
            p = p.next
        return None
我的思路比较直接，用一个数组记录指针走过节点的地址（即指针数组），没走下一步前判断下一个节点在不在路径中，若在，则下一个节点就是环的入口。
编辑于 2020-03-22 22:16:43 回复(0)
Python
朝夕_头像 朝夕_ 
class Solution:
    def EntryNodeOfLoop(self, pHead):
        a = []
        cur = pHead
        while cur:
            if cur not in a:
                a.append(cur)
                cur = cur.next
            else:
                return cur
        return 

发表于 2020-02-29 09:54:31 回复(0)
Python
牛客447097232号头像 牛客447097232号

包含三个问题：

  1. 如何判断是否有环 快慢的指针，走的快的能追上走的慢的说明有环
  2. 有环的话，环上节点的个数，走的快的指针追上走的慢的指针后开始计数，回到这点的时候走过的节点的个数就是环上节点的个数nCycle + 1
  3. 判断环的入口，两个指针，一个nCycle步，速度相同到达同一点的时候说明到达了环的入口 
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None
class Solution:
    def EntryNodeOfLoop(self, pHead):
        if pHead == None:
            return None
        else:

            p1 = pHead
            p2 = p1
            #p1 different speed
            while(p1.next!=None and p1.next.next!=None):
                p1 = p1.next
                p2 = p2.next.next
                if p1 == p2:
                    break
            # no cycle
            if p1.next == None or p1.next.next == None:
                return None
            else:
                # the number of nodes in cycle
                nCycle = 1
                p2 = p2.next
                while(p2 != p1):
                    p2 = p2.next
                    nCycle += 1
            # the entrance
            p1 = pHead
            p2 = pHead
            for i in range(nCycle):
                p2 = p2.next
            while(p1 != p2):
                p1 = p1.next
                p2 = p2.next
            return p1

p1 = ListNode(1)
p1.next = ListNode(2)
p1.next.next = ListNode(3)
p1.next.next.next = ListNode(4)
p1.next.next.next.next = ListNode(5)
p1.next.next.next.next.next = p1.next.next

s =Solution()
s.EntryNodeOfLoop(p1)
编辑于 2020-02-27 00:58:15 回复(0)
提交观点

问题信息

链表 哈希 双指针
难度：
58条回答 129853浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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