首页 > 试题广场 >

链表中环的入口结点

[编程题]链表中环的入口结点
  • 热度指数:641385 时间限制: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,点此查看相关信息
# -*- 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 'null'
        temp = {}
        while pHead != None:
            temp.setdefault(pHead, 0)
            temp[pHead] += 1
            if temp[pHead] == 2:
                return pHead
            pHead = pHead.next
        return 
时间复杂度n
发表于 2019-08-19 13:37:36 回复(0)
更多回答
推荐
如果链表中 有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)

思路:

    设置快慢指针,都从链表头出发,快指针每次走两步,慢指针一次走一步,假如有环,一定相遇于环中某点(结论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 回复(52)
  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)
public ListNode EntryNodeOfLoop(ListNode pHead) {

/*
        //方法一:利用Map
        Map<ListNode,Integer> map = new HashMap();
        ListNode node = pHead;
        while (node != null){
            map.put(node,map.getOrDefault(node,0) + 1);
            if (map.get(node) > 1) return node;
            //或:if (map.get(node) == 2) return node; //一个意思
            node = node.next;
        }
        return null;
*/

        //方法二:利用Set
        Set<ListNode> set = new HashSet();
        while(pHead != null){
            if(set.contains(pHead)) return pHead;
            else set.add(pHead);
            pHead = pHead.next;
        }
        return null;
    }
发表于 2021-08-18 11:41:27 回复(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)
public class Solution {

    public ListNode EntryNodeOfLoop(ListNode head)
    {
        if(head==null||head.next==null){
            return null;
        }
        
        ListNode slow = head;
        ListNode fast = head;
        while(slow!=null&&fast.next!=null){
            slow = slow.next;
            fast= fast.next.next;
            if(slow == fast){
               ListNode temp = head;
                while(temp!=slow){
                    temp = temp.next;
                    slow = slow.next;
                }
                return slow;
                
            }
            
           
            
        }
         return null;
    }
}

发表于 2015-10-03 00:36:18 回复(0)
【转】
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)
    /**
        用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)
F15头像 F15
import java.util.ArrayList;
public class Solution {

    public ListNode EntryNodeOfLoop(ListNode pHead)
    {
    ArrayList <ListNode> list=new ArrayList <ListNode>();  
    list.add(pHead);  
    ListNode curnode=pHead.next;
        if(curnode==null){
            return null;
        }
       while(!list.contains(curnode)){
           list.add(curnode);
           curnode=curnode.next;
       } 
        
        return curnode;
    }
}
没有那么复杂啊,首先要知道,题意里的链表只有一个环,只能有一个环。
形成环无非就是链表的某个节点回到了以前的节点。那么就好办了,把出现过的节点存储到list集合里,每个节点加之前判断一个,是否出现过,即list.contians()方法。
注意:测试用例只有一个节点时候,输出为空;

发表于 2015-11-05 14:26:10 回复(2)
        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)

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)
/*
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)
利用 题目的 对 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)
/*
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)
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)
日常投机取巧
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)
看到找环 想到快慢指针,看到找环入口第一感觉是快慢指针不太适用,要是有个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)
/*
 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)
其实我就很不懂了,不是说好两个输入的吗,怎么就原始代码给一个形参传入??
发表于 2022-02-09 22:03:06 回复(0)
因为 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)