首页 > 试题广场 > linked-list-cycle-ii
[编程题]linked-list-cycle-ii


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?


120个回答

添加回答
推荐
思路:
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 回复(37)
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 回复(1)
/**
思路:
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.首先判断是否存在环
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 回复(0)
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 回复(0)
@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 回复(1)
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 回复(0)

题目描述

Given a linked list, return the node where the cycle begins. If there is no cycle, returnnull.

image

Follow up:

Can you solve it without using extra space?

解题思路

  • 同linked-list-cycle一题,使用快慢指针方法,判定是否存在环,并记录两指针相遇位置(Z);
  • 将两指针分别放在链表头(X)和相遇位置(Z),并改为相同速度推进,则两指针在环开始位置相遇(Y)

image

X,Y,Z分别为链表起始位置,环开始位置和两指针相遇位置。

由于快指针速度为慢指针速度的两倍,那么这个慢指针最多走圆的一圈(这里想象极端情况,就是整个链表就是一个环,那么两个指针从圆的同一个地方出发,那么此时何时相遇呢?必然是慢指针正好才走一圈的时候,快指针走两圈追上来了)。

所以这里假设就是在Z相遇的,那么慢指针走的距离是a+b,很好计算。而快指针走的距离是2(a+b),此时我们想象,假设慢指针走到了X和Z的中间的时候,快指针已经到Z了,那么下面再走的话,就是快指针从Z点出发围着圆绕几圈之后恰好在Z点和X相遇,因此快指针走过的距离是:

2(a+b) = a+b+n*圆的周长 = a+b+n(b+c)

此时a为:

a = (n - 1) * b + n * c = (n - 1)(b + c) +c

从公式上看,当一个指针从X出出发,走完a的距离之后,那么另一个指针从相遇点Z出发就会走(n-1)圈的环再加一个C的距离,此时正好在Y点相遇。

因此,一个指针从头出发,一个指针从相遇点出发,速度相同,相遇点就是环的入口节点。

代码提交

public class Solution {
    public ListNode detectCycle(ListNode head) {
        if(head == null || head.next == 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){
                break;
            }
        }
        //万一没有环的话直接直接返回Null了
        if(fast == null || fast.next == null){
            return null;
        }
        //一个从head开始一步一步走,一个从相遇点开始一步一步走,再相遇就是环的入口位置
        slow = head;
        while(slow != fast){
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }
}
编辑于 2019-03-26 14:58:19 回复(0)
/**
     * 1->2->3->4->[5]->6
     *       |__________|
     * 找到慢指针low和快指针fast相遇的点(没相遇说明没环),
     * 设head到相遇点长为a,相遇点到环入口长为b,环入口到相遇点长为c,
     * low指针走过的长为a,fast走过的长为a+b+c,可得到等式:2a=a+b+c  =>a-c=b
     *
     * @param head
     * @return
*/
public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode low = head, fast = head;
        while (fast != null && fast.next != null) {
            low = low.next;
            fast = fast.next.next;
            if (low==fast){
                fast=head;
                while (fast!=low){
                    fast=fast.next;
                    low=low.next;
                }
                return low;
            }
        }
        return null;
    }
}

发表于 2019-01-21 12:41:15 回复(0)
/*
1.首先利用快慢指针判断链表中是否存在环,当快指针追上慢指针时,说明存在环,否则不存在.
2.计算环中的节点个数。在环中随意选一个节点并以此节点为起点开始遍历,当重复时便得到节点个数n。
3.找到环的入口。定义两个指针p1和p2,p1指向头节点,p2向后移动n步。随后使两个指针以相同的速度向后推进,两个指针重复的节点就是环的入口。
*/
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if(head == nullptr || head->next == nullptr || head->next->next == nullptr)
            return nullptr;
        ListNode *pointerFast = head->next;
        ListNode *pointerSlow = head;
        while(pointerFast != nullptr && pointerFast->next != nullptr && pointerFast != pointerSlow)
        {
            pointerFast = pointerFast->next->next;
            pointerSlow = pointerSlow->next;
        }
        /*不存在环*/
        if(pointerFast == nullptr || pointerFast->next == nullptr)
            return nullptr;
        /*存在环*/
        else
        {
            /*让指针p1指向头节点,指针p2从头节点向后移动n(环中节点个数步)*/
            ListNode *p1 = head;
            ListNode *p2 = head->next;
            pointerFast = pointerFast->next;
            while(pointerSlow != pointerFast)
            {
                pointerFast = pointerFast->next;
                p2 = p2->next;
            }
            /*让p1和p2以g相同的速度向前推进*/
            while(p1 != p2){
                p1 = p1->next;
                p2 = p2->next;
            }
            return p1;
        }
    }
};

发表于 2018-08-16 18:10:55 回复(0)
class Solution {
        //如果环内相遇,则可根据公式2(a+b)=a+b+nr(a代表起点到循环节点的距离,b代表相遇时,距循环
        //节点的距离),计算出此时应该有a = (n-1)r - b(系数n-1可以看做1)即将fast置于起点单步前行会和
        //slow指针相遇
public:
    ListNode *detectCycle(ListNode *head) {
        if(head == NULL || head->next==NULL)
            return NULL;
        ListNode *fast,*slow;
        slow = head;
        fast = head;
        while(fast!=NULL && fast->next!=NULL)
        {
            slow = slow->next;
            fast = fast->next->next;
            //判断是否在环内相遇,若相遇则退出循环
            if(slow == fast)
                break;
        }
        //判断是否存在环,若不存在则直接返回NULL
        if(fast==NULL || fast->next==NULL)
            return NULL;
        fast = head;
        //将fast指针置于头结点,和slow指针同时单步遍历即会相遇在循环节点处
        while(fast != slow)
        {
            slow = slow->next;
            fast = fast->next;
        }
        return fast;
    }
};
发表于 2018-07-08 17:13:21 回复(0)
//很烦,难道入口节点不应该是重复的吗,为什么是重复的前一个。
//我最初写了一个用ArrayList存储的,后来没办法换了快慢指针。我把两种方法都贴出来
//方法一:小众款,我的只能通过40%,有没有道友想用这种方法的可以帮在下一把吗
ArrayList<Integer> at= new ArrayList<Integer>();         if(head==null||head.next==null)             return null;         while(head!=null&&head.next!=null) {             if(!at.contains(head.val)) {                 at.add(head.val);                 head=head.next;             }             else {                 return head;             }         }         return null;
//方法二:大众款
import java.util.*;
public class Solution {
    public ListNode detectCycle(ListNode head) {
        if(head==null)
            return null;
        ListNode fast=head;
        ListNode slow=head;
        while(fast.next!=null&&fast.next.next!=null){
            fast=fast.next.next;
            slow=slow.next;
            if(fast==slow)
                break;
        }
        slow=head;
        if(fast.next==null||fast.next.next==null)
            return null;
        while(fast!=slow){
            fast=fast.next;
            slow=slow.next;
        }
        return slow;
    }
}


发表于 2018-06-09 22:02:56 回复(0)
楼主回答的特别好,思路清晰。
发表于 2018-03-28 20:18:32 回复(0)
解法:一个快指针,两个慢指针。
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 回复(0)
/****************************************************************************************************************
置顶的回答 解法已经详细说明了
  我的解法不同的地方在于对于循环的判断,比他的更加简单,不需要跳出循环来进行判断
******************************************************************************************************************/
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if(head==NULL)
            return NULL;
        ListNode* runner = head;
        ListNode* chaser = head;
        while(runner!=NULL&&runner->next!=NULL){
            runner = runner->next->next;
            chaser = chaser->next;
            if(runner == chaser) {
                chaser = head;
                while(chaser!=runner){
                    chaser=chaser->next;
                    runner=runner->next;
                }
                return runner;
            }//if
        }//while
        return NULL;
    }
};
发表于 2018-03-02 16:41:12 回复(0)
public ListNode detectCycle(ListNode head) {
        if(head == null) return null;
        ListNode slow = head;
        ListNode fast = head;
        while(slow!=null && fast!=null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
            if(slow == fast){
                //has cycle
                ListNode p = head;
                while(p!=slow){
                    p = p.next;
                    slow = slow.next;
                }
                return p;
            }
        }
        return null;
    }


发表于 2017-12-13 13:53:56 回复(0)
public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode s = head;//定义慢指针
        ListNode f = head;//定义快指针
        if(head==null||head.next==null)//head不存在或者只有head一个节点,无环返回
            return null;
        while(f!=null&&f.next!=null)//快指针及其next不为空则快指针走两步,慢指针走一步
            {
            f = f.next.next;
            s = s.next;
            if(f==s)//两指针相等,说明有环并退出循环,慢指针保存相遇节点
                break;
        }
        if(f==null||f.next==null)//若快指针或者他的next为空,说明无环
            return null;
        else   //否则将快指针设为head
            f = head;
        while(f!=s)//存在环时,快指针从头节点出发,慢指针从相遇节点出发,每次走一步,相遇节点即为环的入口节点
            {
            f = f.next;
            s = s.next;
        }
        return s;
    }
}

发表于 2017-09-12 10:09:44 回复(0)
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)

思路:本题与 Linked List Cycle 类似,一样是申请两个指针slow和fast

slow指针一次走一步,fast走两步。

现在假设存在环,设从head走A步到达环的入口节点,第一次相遇时,slow在环内走了B步(slow一共走了A+B步),

当fast和slow指针第一次相遇时,slow走了A+B步,那么fast走过的距离是slow的两倍,即2*(A+B),、

此时,fast和slow的距离正好相差一个环的距离,即2*(A+B)=A+B+C(设C为环的大小),得C=A+B

此时,slow只要再走C-B步就可以走到环的入口(因为环的大小是C,slow已经在环内走了B步),有由C=A+B得到C-B=A,

即,如果此时有一个新的指针node,从head出发,当slow和head相遇时,相遇的点就是环的入口点

package go.jacob.day818;

/**
 * 142. Linked List Cycle II
 * 
 * @author Jacob 题意:删除环的第一个节点,不存在环则返回null
 */
public class Demo2 {
	public ListNode detectCycle(ListNode head) {
		if (head == null)
			return null;
		ListNode slow = head;
		ListNode fast = head;
		while (fast.next != null && fast.next.next != null) {
			slow = slow.next;
			fast = fast.next.next;
			//slow被fast追上
			if(slow==fast){
				//从头结点出发
				ListNode node=head;
				while(node!=slow){
					node=node.next;
					slow=slow.next;
				}
				return node;
			}
		}
		return null;
	}
} 


编辑于 2017-08-18 12:17:38 回复(0)
public class Solution {
    public ListNode detectCycle(ListNode head) {
		if(head == null || head.next == null) return null;
		ListNode slow = head;
		ListNode fast = head;
		boolean hasCycle = false;
		while (fast != null && fast.next != null) {
			slow = slow.next;
			fast = fast.next.next;
			if(slow == fast) {
				hasCycle = true;
				break;
			}
		}
		if(hasCycle) {
			fast = head;
			while (slow != fast) {
				slow = slow.next;
				fast = fast.next;
			}
			return slow;
		}
		return null;
	}
}

发表于 2017-07-13 21:31:32 回复(0)
class Solution {
public:
    ListNode *detectCycle(ListNode *head)
    {
        if(!head)
            return nullptr;
        ListNode *fast= head,*slow = head;
        while(fast->next && fast->next->next)
         {
            slow = slow->next;
            fast = fast->next->next;
            if(slow == fast)
            {
                slow = head;
                while(slow != fast)
                {
                    fast = fast->next;
                    slow = slow->next;
                }
                return slow;
            }
        }
        return nullptr;
    }
};

发表于 2017-07-04 11:45:47 回复(0)