首页 > 试题广场 >

链表中环的入口节点

[编程题]链表中环的入口节点
  • 热度指数：134760 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
对于一个给定的链表，返回环的入口节点，如果没有环，返回null
拓展：
你能给出不利用额外空间的解法么？


说明：本题目包含复杂数据结构ListNode，点此查看相关信息
算法知识视频讲解
添加回答
推荐
wangxiaobao头像 wangxiaobao
思路：
1）同linked-list-cycle-i一题，使用快慢指针方法，判定是否存在环，并记录两指针相遇位置(Z)；
2）将两指针分别放在链表头(X)和相遇位置(Z)，并改为相同速度推进，则两指针在环开始位置相遇(Y)。

证明如下：
如下图所示，X,Y,Z分别为链表起始位置，环开始位置和两指针相遇位置，则根据快指针速度为慢指针速度的两倍，可以得出：
2*(a + b) = a + b + n * (b + c)；即
a=(n - 1) * b + n * c = (n - 1)(b + c) +c;
注意到b+c恰好为环的长度，故可以推出，如将此时两指针分别放在起始位置和相遇位置，并以相同速度前进，当一个指针走完距离a时，另一个指针恰好走出 绕环n-1圈加上c的距离。
故两指针会在环开始位置相遇。 

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if(head == NULL){
            return 0;
        }
        ListNode* slow = head;
        ListNode* fast = head;
        while(fast != NULL && fast->next != NULL){
            slow = slow->next;
            fast = fast->next->next;
            if(slow == fast){
                break;
            }
        }
        if(fast == NULL || fast->next == NULL){
            return NULL;
        }
        slow = head;
        while(slow != fast){
            slow = slow->next;
            fast = fast->next;
        }
        return slow;
    }
};

编辑于 2016-08-07 13:48:35 回复(51)
M00N头像 M00N 
package linkedlist;
/**
 * 题目描述: 链表的入环节点，如果无环，返回null
 * Given a linked list, return the node where the cycle begins. If there is no cycle, returnnull.
 * Follow up: Can you solve it without using extra space?
 * 思路：
 * 1）首先判断是否有环,有环时，返回相遇的节点，无环，返回null
 * 2）有环的情况下， 求链表的入环节点
 *   fast再次从头出发，每次走一步，
 *   slow从相遇点出发，每次走一步，
 *   再次相遇即为环入口点。
 * 注：此方法在牛客BAT算法课链表的部分有讲解。
 */
//nowcoder pass
public class Solution {
	
    public ListNode detectCycle(ListNode head) {
    	if (head == null) {
    		return null;
    	}
    	
    	ListNode meetNode = meetingNode(head);
    	if (meetNode == null) {//说明无环
    		return null;
    	}
    	
    	ListNode fast = head;
    	ListNode slow = meetNode;
    	while (slow != fast) {
    		slow = slow.next;
    		fast = fast.next;
    	}
    	
    	return slow;
    }
    
    //寻找相遇节点，如果无环，返回null
    public ListNode meetingNode(ListNode head) {
    	ListNode slow = head;
    	ListNode fast = head;
    	while (fast != null && fast.next != null) {
    		slow = slow.next;
    		fast = fast.next.next;
    		if (slow == fast) {
    			return slow;
    		}
    	}
    	return null;
    }
}

发表于 2017-04-02 20:03:03 回复(12)
顾翅头像 顾翅

来个不一样的思路：
1.首先判断是否存在环
2.若存在环，则从起点开始，每走一步就删除上一个节点的next指针，最后一个节点就是环的起点。因为环的起点会存在两个next指向它。

ListNode *detectCycle(ListNode *head) {//每次前进的时候删除上一个指针
        if(head==NULL||head->next==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)
                break;
        }
         if(fast == NULL||fast->next==NULL)
            return NULL;

        ListNode * pre=head;
        ListNode*cur=head->next;
        while(cur!=NULL){
            if(pre==cur)
                return pre;
            pre->next=NULL;
            pre=cur;
            cur=cur->next;
        }
        return pre;

    }
发表于 2018-05-13 22:08:09 回复(9)
Butterfliesflyaway↘头像 Butterfliesflyaway↘ 
public class Solution {
    /*
     * 思路：
     * 1）首先判断是否有环，有环时，返回相遇的节点，无环，返回null
     * 2）有环的情况下，求链表的入环节点
     *    fast再次从头出发，每次走一步，slow从相遇点出发，每次走一步，再次相遇即为环入口点。
     */
    public ListNode detectCycle(ListNode head) {
        if(head == null) return null;
        
        ListNode slow = head;
        ListNode fast = head;
        ListNode meetNode = null;
        while(fast!=null && fast.next!=null) {
            slow = slow.next;
            fast = fast.next.next;
            if(slow == fast) { //快慢指针相遇，说明有环，记录相遇节点，跳出循环
                meetNode = slow;
                break;
            }
        }
        if(meetNode == null) return null; //相遇节点为空，说明无环，返回null
        
        fast = head; //fast再次从头出发
        while(slow != fast) { //再次相遇即为环入口点
            slow = slow.next; //slow每次走一步
            fast = fast.next; //fast每次走一步
        }
        return slow;
    }
}

发表于 2019-01-03 17:27:18 回复(3)
xsk头像 xsk
看了别人的图，画的很清晰，但是感觉数学公式应该这样写：

slow： 走过 x 个节点
fast：走过2x 个节点
第一次相遇时，2x-x = b+c；    (1)
slow走过的距离为 x = a + b + n*(b + c);   (2)
由(1)(2)可得 b+c = n*(b+c) + a + b；
n>0时，a+b = (1-n)*(b+c) <= 0,不成立。故n = 0,得出：a = c。

编辑于 2018-09-14 22:24:11 回复(4)
心海盗梦头像 心海盗梦 
/**
思路：
1.还是先用快慢指针方法，找出快慢指针相遇的点；
2.重新定义两个指针，一个为head，另一个为快慢指针相遇点；
3.两个指针每次走一步，相遇点则是链表环的起点；
*/
public class Solution {
    public ListNode detectCycle(ListNode head) {
        if(head == null){
            return null;
        }
        ListNode slow = head;
        ListNode fast = head;
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
            if(slow == fast){
                ListNode node1 = head;
                ListNode node2 = fast;
                while(node1 != node2){
                    node1 = node1.next;
                    node2 = node2.next;
                }
                return node1;
            }
        }
        return null;
    }
}

发表于 2017-06-16 16:24:18 回复(2)
会飞的香蕉头像 会飞的香蕉
解法：一个快指针，两个慢指针。
1.快慢指针同时出发，如果快指针到达null，说明链表没有环
2.如果快慢指针相遇了，说明链表有环。
3.在快慢指针相遇的时候，让第二个慢指针从头结点出发，
4.当两个慢指针相遇的时候，相遇的位置就是环的起点。
原理：

图画的戳了一点，咳咳：
0.假设链表有环，并且环之前的部分长n，环周长m，慢指针速度为1，快指针速度为2。环为顺时针
1.首先快指针和慢指针一起从F0S0出发。
当慢指针经过n的距离到达环的起点S1的时候，快指针走过2n的距离到达F1。
2.快指针此时共走了2n的距离，在环上走了n的距离，
因此快指针此时距离环的起点n%m这么多(按顺时针计算)。
也就是说，快针要追上慢针需要多走m-n%m(即从F1顺时针回到S1的距离)
3.也就是说，当快指针追上慢指针的时候，慢指针从S1走了m-n%m到达S2F2。
该点距离环的起点S1有n%m这么多距离。(快指针有多少路要追，慢指针就会从起点走多少路)
4.快慢指针在S2F2相遇的时候，另一个慢指针2 从F0S0出发。
慢指针1走到S1要经过n%m。
慢指针2此时离环起点S1 n-n%m。该距离可以被m整除。
因此两个慢指针一定会在S1相遇。
代码
class Solution { 

public:


  ListNode *detectCycle(ListNode *head) {


  if(!head)return nullptr;


  if(!head->next)return nullptr;


  ListNode *pSlow = head;


  ListNode *pSlow2= head;


 ListNode *pFast = head;


  while(pFast&&pFast->next)


  {


  pSlow = pSlow->next;


  pFast = pFast->next->next;


  if(pFast==pSlow)


  break;


  }


  if(!pFast||!pFast->next)


 {//reach end


  return nullptr;


 }


  else


  {//loop


 while(pSlow2 != pSlow)


  {


 pSlow2 = pSlow2->next;


  pSlow = pSlow->next;


  }


 return pSlow2;


 }


  }


};
编辑于 2018-03-15 17:13:05 回复(1)
ahuangliang头像 ahuangliang
@wangxiaotao的图不错，借用一下，公式不太清楚。
串长a + n，其中n为循环，当a + b步的慢指针与快指针相遇时，快指针已经走过了k圈。
即a + b + k * n = 2 * (a+b)，求a，得到a = k * n - b。
也就是X走a步，等于Z位置上的指针再走k圈，相遇于Y点。 

ListNode *detectCycle(ListNode *h) {
        ListNode *p = h, *q = h; 
        while (q && q->next) {
            p = p->next;
            q = q->next->next;
            if (p == q) {
                while (h != q) {
                    q = q->next;
                    h = h->next;
                }
                return h;
            }
        }
        
        return NULL;
    }

编辑于 2016-05-05 21:54:54 回复(5)
Python
wengJJ头像 wengJJ
Python
a为起点到环起点的距离，b为环内相遇时距离环起点距离
慢指针走的路程a+b,快指针为2(a+b),举个例子慢指针走到第二个节点时，快节点已经走到第四个节点了，以此类推
有环则会相遇（待证明），则快慢指针的相差距离就是以环为单位，2(a+b)-(a+b) = n*环长度 
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

#
# 
# @param head ListNode类 
# @return ListNode类
#
class Solution:
    def detectCycle(self , head ):
        # write code here
        if not head:
            return None
        slow = head
        fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                node1 = head
                node2 = slow
                while node1 != node2:
                    node1 = node1.next
                    node2 = node2.next
                return node1
        return None


发表于 2021-05-24 14:48:39 回复(0)
Python
splwany头像 splwany

python版：

class Solution:
    def detectCycle(self , head ):
        if not head:
            return None
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow is fast:
                slow = head
                while slow is not fast:
                    slow = slow.next
                    fast = fast.next
                return fast
        return None
发表于 2021-03-07 11:58:43 回复(0)
C/C++
nbgao头像 nbgao 
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
    	if(head == NULL)
    		return NULL;
    		
        ListNode *p = head, *q = head;
        while(q && q->next)
        {
        	p = p->next;
        	q = q->next->next;
			if(p == q)
			{
				while(q != head)
				{
					q = q->next;
					head = head->next;
				}
				return head;
			}
		} 
		return NULL;
    }
};

发表于 2017-08-19 04:13:30 回复(0)
L.Over头像 L.Over
唉，全靠记方法
发表于 2021-04-17 22:51:24 回复(0)
暁仨畀头像 暁仨畀
分享一个不一样的解题思路。
1 快慢指针找出是否存在环
2 重新出发p每次前进时，打断自己走过的路径。当他走过一圈回到入环点时会发现前路已空。因为已经确定有环，所以最后p.next为空时，p为切入点 
public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode p=head,q=head;
        if(p==null) return null;
        while(true){
            if(p.next==null) return null;
            else if(p.next.next==null) return null;
            p=p.next.next;
            q=q.next;
            if(p==q) break;
        }
        if(head.next==head) return head;
        for(q=head,p=head.next;p!=null;p=p.next){
            q.next=null;
            q=p;
        }
        return q;
    }
}

发表于 2021-04-12 14:57:13 回复(0)
静静流淌头像 静静流淌 
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        if(head == null)
            return null;
        ListNode fast = head;
        ListNode slow = head;
        boolean isRing = false;
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
            if(fast == slow){
                isRing = true;
                break;
            }  
        }
        if(!isRing)
            return null;
        fast = head;
        while(fast != slow){
            fast = fast.next;
            slow = slow.next;
        }
        return fast;    
    }
}

发表于 2021-03-30 09:42:43 回复(0)
Java
叫我骑天大圣头像 叫我骑天大圣 
环儿的入口结点：从head起，第一个在环儿里的结点。

思路：爱的暴力转圈圈，时间复杂度O((n-m)*m)，n=链表长度，m=环的长度；最坏接近O(n^2)

    1）定义一对快慢指针，先让两个指针进入环中。
    若指针走的过程中转角遇到空null结点，说明没有环，return null即可。唉！没找到爱的圈圈。
    
    2）两个指针进入环中相遇后，进入下一步找环入口操作：
    从head依次往后枚举判断当前枚举的结点是否在环中，判断方法：
    让环中指针在环内转圈，若途中遇到了当前枚举的结点，说明该结点在环中。
    找到第一个这样的结点就是入口结点。
public ListNode detectCycle(ListNode head) {
        if(head!=null){
            ListNode first=head,second=head.next,start;//定义指针
            //尝试把指针拉入环中
            while(first!=second){
                if(first==null||second==null||second.next==null) return null;//没环
                first=first.next;
                second=second.next.next;
            }
            //有环
            //找环入口：从head起依次往后枚举，第一个在环里的结点就是环的入口结点
            start=second;//标记环起点
            first=head;
            while(first!=null){
                //second指针在环里转一圈，查看当前结点first是否在环里
                do{
                    if(second==first) return first;//找到的第一个就是结果
                    second=second.next;
                }while(second!=start);//转一圈退出
                first=first.next;//枚举下一个
            }
            return null;
        }
        return null;
    }

编辑于 2021-03-27 11:39:59 回复(0)
Java
佛系**头像 佛系** 
//思路：和判断是否有环解法一致，将遍历后的节点指向一个新增节点，如果遍历过程中，某个节点指向了那个节点，那么这个节点就是入口节点（即交叉点）。



public static ListNode detectCycle(ListNode head) {
        ListNode target = new ListNode(-1);
        ListNode cur = head;
        while(cur != null) {
            if(cur.next == target) {
                return cur;
            }
            ListNode next = cur.next;
            cur.next = target;
            cur = next;
        }
        return null;
    }

发表于 2021-03-08 15:26:53 回复(0)
大厂给个offer罢头像 大厂给个offer罢
public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode pre;
        while(head != null){
            if(head.next == head){
                return head;
            }
            pre = head.next;
            head.next = head;
            head = pre;
        }
        return null;
    }
}
发表于 2021-03-08 14:26:51 回复(0)
Java
卡在狗嘴里的象牙头像 卡在狗嘴里的象牙
发表于 2020-11-27 12:11:59 回复(0)
实在学不动了头像 实在学不动了
1.用指针temp指向当前待确定的节点,用pre指向待确定节点的上一个节点。由于在遇到环的入口之前，前面的节点均不可能重复，所以待确定节点的上一个节点一定还未遇到。那么每次从头节点开始，至待确定节点的前一个节点，用指针依次遍历，在此之间如果指向地址等于待确定节点地址，则说明待确定节点第二次遇到，为环，入口即为待确定节点。
2.在1中的思路无法解决环的入口就是头节点的问题，1中待确定点从head->next开始，所以还要额外判断head是否为入口，解决办法是当待确定节点为head时，即可判定head为环入口

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if(!head) return NULL;
        ListNode *temp,*top,*pre;
        temp=head->next;//待确定结点
        top=head;  
        pre=head;  //待确定节点前一个节点（用这个节点的原因如1中介绍，待确定节点的前一节点是独一无二的，便于判断）
        bool flag=false;
        while(temp) {
            while(top!=pre) {
                top=top->next;  //如果还未到待确定节点前一节点就继续
                if(top==temp) flag=true;  //判断除head外其他结点有无可能是入口
            }
            if(flag) return temp;  //返回入口
            else {
                pre=pre->next;
                temp=temp->next;
                if(temp==head) return head;  //判断head有无可能是入口
            }
            top=head;
        }
        return NULL;
    }
};

发表于 2020-04-19 17:57:43 回复(0)
AriesLi头像 AriesLi 
public class Solution {
    public ListNode detectCycle(ListNode head) {
        /* 快慢指针，第一次相遇快指针走过的是慢指针的两倍
         * head到环起始位置为l, 环周长为r, 第一次相遇点在环起点后x
         * s = l + x; 2s = l + r + x; => l + x = r; => l = r - x;
         * 同时从head和第一次相遇点往后走，相遇位置即为环起点
        */
        ListNode fast = head;
        ListNode slow = head;
        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 = head;
        while(slow != fast){
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }
}

发表于 2019-12-30 16:50:26 回复(0)
Java
CQFly头像 CQFly 
/** 一个新思路，可能没有满足不使用额外空间的要求，不过使用的也不多
    毕竟大多数牛友所述的Floyd判圆算法不是第一次就能够轻易想出来的

    1. 先利用快慢指针判断是否存在环，并在这个过程中对快指针走过的结点数计数，假设为2*count
    2. 从链表中第一个结点开始指定，依次让慢指针走2*count步，如果没有与指定结点相遇，就让指定结点向后移动
    3. 当第一次出现慢指针与指定结点相遇的情况时，该结点即为环入口，返回该结点即可
    */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode onestep=head;
        ListNode twostep=head;
        ListNode p=head;
        long count=0;
        while(twostep!=null && twostep.next!=null){
            onestep=onestep.next;
            twostep=twostep.next.next;
            count++;
            if(onestep==twostep){
                while(true){
                    for(int i=0;i<count*2;i++){
                        onestep=onestep.next;
                        if(onestep==p){
                            return p;
                        }
                    }
                    p=p.next;
                }
            }
        }
        return null;
    }
}

发表于 2019-11-21 13:25:55 回复(0)
提交观点

问题信息

链表 双指针
难度：
241条回答 37306浏览

热门推荐

通过挑战的用户

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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