我要招人

去企业版

首页 > 试题广场 >

链表中环的入口节点

[编程题]链表中环的入口节点

热度指数：134760 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

对于一个给定的链表，返回环的入口节点，如果没有环，返回null

拓展：

你能给出不利用额外空间的解法么？

说明：本题目包含复杂数据结构ListNode，点此查看相关信息

算法知识视频讲解

查看答案及解析

推荐

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)

Python

求求给孩子一个offer吧

class Solution:
def detectCycle(self , head ):
# write code here
if not head:
return None
fast = head
slow = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next

if(fast == slow):
while(head!=slow):
head=head.next
slow = slow.next
return head
return None

发表于 2021-07-09 23:57:43 回复(0)

Python

code_of_yang

#方法一，利用集合
class Solution:
    def detectCycle(self , head ):
        my_set = {''}
        while head != None:
            if head in my_set:
                return head
            else:
                my_set.add(head)
            head = head.next
        return None
'''
#方法二，逐个删除
class Solution:
    def detectCycle(self , head ):
        while head != None:
            if head == head.next:
                return head
            tmp_node = head.next
            head.next = head
            head = tmp_node
        return None
'''
        # write code here

不知道什么毛病，第二种逐个删除就是报错

编辑于 2021-05-29 15:41:36 回复(0)

Python

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

橘子猪

class Solution:
    def detectCycle(self, head):
        while head:
            if head.next == head:
                return head
            head.next, head = head, head.next
        return None

将之前遍历的节点的next全部指向自己，当节点中有环的时候，入口会遍历两次，因此找到指向自己的节点就是入口

发表于 2021-04-12 22:38:10 回复(0)

Python

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)

Python

dryisfinished

# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None

#
#
# @param head ListNode类
# @return ListNode类
#
class Solution:
def detectCycle(self , head ):
if head is None:
return
low=head
fast=head
dd=head
while True:
if not fast.next or not fast.next.next:
return None
low=low.next
fast=fast.next.next
if low==fast:
while True:
if dd==low:
return dd
dd=dd.next
low=low.next

# write code here

发表于 2021-01-02 13:52:52 回复(0)