AcWing 34. 链表中环的入口结点

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 34. 链表中环的入口结点原题链接中等

作者：

yxc , 2019-01-06 17:41:34 , 所有人可见 , 阅读 11320

95

67

算法

(链表，快慢指针扫描) $O(n)$

本题的做法比较巧妙。
用两个指针 $first, second$ 分别从起点开始走， $first$ 每次走一步， $second$ 每次走两步。
如果过程中 $second$ 走到null，则说明不存在环。否则当 $first$ 和 $second$ 相遇后，让 $first$ 返回起点， $second$ 待在原地不动，然后两个指针每次分别走一步，当相遇时，相遇点就是环的入口。

QQ图片20180531162503.png

证明：如上图所示， $a$ 是起点， $b$ 是环的入口， $c$ 是两个指针的第一次相遇点， $ab$ 之间的距离是 $x$ ， $bc$ 之间的距离是 $y$ 。
则当 $first$ 走到 $b$ 时，由于 $second$ 比 $first$ 多走一倍的路，所以 $second$ 已经从 $b$ 开始在环上走了 $x$ 步，可能多余1圈，距离 $b$ 还差 $y$ 步（这是因为第一次相遇点在 $b$ 之后 $y$ 步，我们让 $first$ 退回 $b$ 点，则 $second$ 会退 $2y$ 步，也就是距离 $b$ 点还差 $y$ 步）；所以 $second$ 从 $b$ 点走 $x + y$ 步即可回到 $b$ 点，所以 $second$ 从 $c$ 点开始走，走 $x$ 步即可恰好走到 $b$ 点，同时让 $first$ 从头开始走，走 $x$ 步也恰好可以走到 $b$ 点。所以第二次相遇点就是 $b$ 点。

另外感谢@watay147提供的另一种思路，可以用公式来说明： $a, b, c, x, y$ 的含义同上，我们用 $z$ 表示从 $c$ 点顺时针走到 $b$ 的距离。则第一次相遇时 $second$ 所走的距离是 $x + (y + z) * n + y$ , $n$ 表示圈数，同时 $second$ 走过的距离是 $first$ 的两倍，也就是 $2(x + y)$ ，所以我们有 $x + (y + z) * n + y = 2(x + y)$ ，所以 $x = (n - 1) \times (y + z) + z$ 。那么我们让 $second$ 从 $c$ 点开始走，走 $x$ 步，会恰好走到 $b$ 点；让 $first$ 从 $a$ 点开始走，走 $x$ 步，也会走到 $b$ 点。

时间复杂度

$first$ 总共走了 $2x + y$ 步， $second$ 总共走了 $2x + 2y + x$ 步，所以两个指针总共走了 $5x + 3y$ 步。由于当第一次 $first$ 走到 $b$ 点时， $second$ 最多追一圈即可追上 $first$ ，所以 $y$ 小于环的长度，所以 $x+y$ 小于等于链表总长度。所以总时间复杂度是 $O(n)$ 。

C++ 代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *entryNodeOfLoop(ListNode *head) {
        if (!head || !head->next) return 0;
        ListNode *first = head, *second = head;

        while (first && second)
        {
            first = first->next;
            second = second->next;
            if (second) second = second->next;
            else return 0;

            if (first == second)
            {
                first = head;
                while (first != second)
                {
                    first = first->next;
                    second = second->next;
                }
                return first;
            }
        }

        return 0;
    }
};

39 评论

liweidong 2022-11-08 17:14

#### 一种小聪明的的方法

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *entryNodeOfLoop(ListNode *head) {

        while(head){
            if(head->val > 1000){
              head->val -= 1000;
              return head;  
            } 
            head->val += 1000;
            head = head->next;
        }
        return NULL;

    }
};

流浪宇航员 2023-02-02 00:51

牛逼

没那么多因果 2023-02-18 14:26 回复了流浪宇航员的评论

66h

求求你别学了 2023-04-04 11:51

思路好呀hhh

Popcorn_code 2023-04-22 20:46

吊爆了

RwChen 2023-09-18 08:46

可以，面向测试用例编程

就你也想和老爹过过手吗 2023-10-02 23:38

牛逼，利用val的范围，相当于将走过的节点标记了，第二次走就会被发现哈哈哈哈

快来offer吧 6个月前

class Solution {
public:
ListNode entryNodeOfLoop(ListNode head) {
if(head==NULL)return head;
vector[HTML_REMOVED] arr(510,0);
auto p=head;
while(p){
arr[p->val]++;
if(arr[p->val]>1){
//cout<<;
break;
}
p=p->next;
}
p->val;
return p;

};

我是你的改进版hhh

PiSir 2021-08-02 00:03

### 哈希表真好用，哈哈

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def entryNodeOfLoop(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        ids = {}
        k=1000

        while k>0 and head:
            if id(head) in ids:
                return head
            ids[id(head)]=1
            head = head.next
            k-=1
        return None

Macre 2024-01-07 17:50

就题而论，hash，确实简单

class Solution {
public:
    ListNode *entryNodeOfLoop(ListNode *head) {
        int N[1010] = {0};
        while(head){
            if(!N[head->val]) N[head->val] = 1;
            else return head;
            head = head->next;
        }
        return NULL;

    }
};

silverbullet 2023-04-16 20:45

用哈希表确实简单

class Solution {
public:
    ListNode *entryNodeOfLoop(ListNode *head) {
        unordered_set<ListNode*> s;
        for(auto p = head;p!=nullptr;p = p->next)
        {
            if(!s.insert(p).second)return p;
        }
        return nullptr;
    }
};

Richelieu_1 2023-01-17 22:46

为什么我用访问数组写，说我超时呢？
求大佬指教！
/
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode next;
* ListNode(int x) : val(x), next(NULL) {}
* };
/
class Solution {
public:
ListNode entryNodeOfLoop(ListNode head) {
vector[HTML_REMOVED]vis(505,-1);
auto p=head;
auto q=head;
while(p&&vis[p->val]==0){
vis[p->val]=1;
p=p->next;
}

     return p;
}

};

掘掘子来惹 2022-02-10 13:37

第一次相遇后，第二次相遇前，first和second的速度变成一样的了？

CyanFishhh 2022-02-16 20:48

是的，就是需要一样的，速度要改回来，画个图很清楚的

Acwing_九日 2021-02-19 22:16

class Solution {
public:
    ListNode *entryNodeOfLoop(ListNode *head) {
        if (!head) return nullptr;

        auto fast = head, slow = head;
        while (fast && fast->next && fast != slow) {
            fast = fast->next->next;
            slow = slow->next;
        }
        if (!fast || !fast->next) return nullptr; //无环
        slow = head;
        while (fast != slow) {
            fast = fast->next;
            slow = slow->next;
        }

        return fast;
    }
};

这样写为什么wrong answer啊？求各位大佬帮忙解释一下

白胡子的花猫 2021-03-18 20:11

因为你第一个循环都不能进入，刚开始的时候你的定义fast是等于slow的

Acwing_九日 2021-03-18 20:19 回复了白胡子的花猫的评论

奥~懂了懂了，昏头了，谢谢大佬指点

futz12 2021-01-14 13:32

class Solution {
public:
ListNode entryNodeOfLoop(ListNode head) {
ListNode *now=head;
while(now!=NULL)
{
if(now->val<0)
{
now->val=-now->val;
return now;
}
else
{
now->val=-now->val;
now=now->next;
}
}

    return NULL;

}

};

//没想到吧

@谁是凶手1703 2021-01-09 21:59

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *entryNodeOfLoop(ListNode *head) {
         ListNode* first=head;
        ListNode* second=head;
        while(first && second)
        {
            first = first->next;
            second=second->next;
            if(second->next) second=second->next;
            else return NULL;
            if(first == second)
                break;
        }
        second=head;
        while(first!=second){
            first=first->next;
            second=second->next;
        }
        return first;
    }
};

这样写acwing可以过，牛客不可哎

喜欢瞪太阳 2021-09-18 14:54

acwing的数据还是稍水了一点

远跋 2021-01-02 18:37

我是这样写的哈：

class Solution {
public:
    ListNode *entryNodeOfLoop(ListNode *head) {
        if(!head) return nullptr;
        ListNode* l = head; ListNode* r = head;
        while(r && r->next) {
            r = r->next->next; l = l->next;
            if(r == l) {
                r = head;
                while(l != r) {
                    l = l->next; r = r->next;
                }
                return l;
            }
        }
        return nullptr;
    }
};

Arroz 2020-11-15 15:20

first = first->next;
            second = second->next;
            if (second) second = second->next;
            else return 0;

y总，这一段while循环里面的if条件我觉得应该是second->next,因为如果链表没有环且有偶数个节点，最后second就越界了。

温柔的木头Crystal 2020-11-10 16:46

这个代码有什么问题呢
/
Definition for singly-linked list.
class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
next = null;
}
}
/
class Solution {
public ListNode entryNodeOfLoop(ListNode head) {
if(head==null||head.next==null) return null;
ListNode first=head;
ListNode second=head;
while(first!=null&&first!=second)
{
first=first.next;
second=second.next;
if(second!=null)
second=second.next;
else return null;
}

first=head;
while(first!=second)
{
first=first.next;
second=second.next;
}
return first;
}
}

Timi 2020-11-11 17:33

while(first!=null&&first!=second)，上两行不是把first和second都赋值成head了吗
改成while(first!=null && second != null)

温柔的木头Crystal 2020-11-11 19:54 回复了 Timi 的评论

突然明白，谢谢大佬，昨天想了一个多小时！

18108352172 2020-07-31 17:23

y总，我想问下if (!head || !head->next) return 0;不是保证了链表为空或者只有一个结点的话输出null，那为什么输入[1],0,时，还能输出1呀，不应该是null？

yxc 2020-08-18 14:44

输入[1], 0表示一个包含一个点的自环。输入[1], -1才表示一个长度是1的链表。

KID_22 2020-04-24 18:54

可以直接用map，也通过了，代码如下：

class Solution {
public:
    ListNode *entryNodeOfLoop(ListNode *head) {
        map<ListNode*,int> mp;
        while(head)
        {
            if(mp[head])
                return head;
            mp[head]=1;
            head=head->next;
        }
        return NULL;
    }
};

yxc 2020-05-12 18:32

可以的，不过map会多用 $O(n)$ 空间，而且时间也会多一个 $O(logn)$ 。

南京伪学霸 2019-09-28 16:00

爱上这个网站了如果大佬用的是python就好了

yxc 2019-09-28 21:46

哈哈加油，活动页面里有不少其他同学打卡的python代码~

Cheney 2019-07-04 19:20

求助大佬，为什么我的代码的输出结果不对呢？
样例中输出编号为2的结点val 3，我输出了编号为4的val 5

class Solution {
public:
    ListNode *entryNodeOfLoop(ListNode *head) {
        if(!head || !head->next) return 0;

        ListNode *fast = head;
        ListNode *slow = head;
        ListNode *meet = NULL;

        while(fast){ //偶数次退出
            slow = slow->next;
            fast = fast->next;
            if(!fast)  return 0; //奇数次退出

            fast = fast->next;

            if(fast == slow){
                meet = slow;
                break; //相遇
            }
        }

        while(head && meet){
            if(head == meet) return head;
            head = head->next;
            slow = slow->next;
        }

        return NULL;        
    }
};

CH_9 2019-03-13 20:22

if (first == second)
{
        first = head;
        while (first != second)
        {
              first = first->next;
              second = second->next;
        }
        return first;
}

second不是应该走两步嘛，为什么不是second=second->next->next