剑指offer - 链表中环的入口结点

发表于 | 更新于

题目

https://www.nowcoder.com/questionTerminal/253d2c59ec3e4bc68da16833f79a38e4

题意

一个链表中包含环，请找出该链表的环的入口结点。

题解

  • 方法一
    那个set存放每个节点，如果遍历链表时，遇到set中有的节点，那他就是环的入口。这种方法不仅需要额外的空间，还需要每次判断节点是否在set中，效率低下。
  • 方法二
    断链法。用两个指针，p1在前，p2紧随其后，每次p1移动，都将p2的next置为NULL，这样当找到尾节点时，就是环的入口。
    不过这种方法会破坏链表的结构。并且还有一个问题，这种方法没有办法判断是否有环，没有环的输入会返回最后一个节点，所以，我认为并不能算正确。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};

class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead)
    {
        if(pHead==NULL) return NULL;
        ListNode *p1=pHead,*p2=pHead;
        while(p1->next){
            p1=p1->next;
            p2->next=NULL;
            p2=p1;
        }
        return p2;
    }
};
  • 方法三
    快慢指针。一个快指针fast，一个慢指针slow，起点均为头节点，fast移动速度是slow移动速度的两倍。如果没有环，两者不会相遇，fast就会碰到NULL，如果有环，那么两者一定会相遇，并且相遇的点一定在环上。
    如图，A为起点，B为环的入口，C为fast和slow相遇的点。
    p1
    相遇时，假设slow走的距离是X，fast为2X,fast比slow多走的一定是环长度的整数倍，假设环长度为L,多走的就是kL，2X-X=kL,也就是shuoslow走的距离是kL，假设链表断开环的长度为N。
    也就是图中，A和C的长度为kL，如果此时两个指针p1和p2，一个在A点，一个在C点，那么两个相同速度行进，再经过kL的路程，两个都会到C点，而且最后的B到C之间的路是携手共进的，所以其实当两者相遇时，我们就已经确定了环的入口，就是B。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};

class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead)
    {
        if(pHead==NULL) return NULL;//链表为空
        bool flag=true;
        ListNode *p1=pHead,*p2=pHead;
        do{
            p2=p2->next;
            flag=!flag;
            if(flag)
                p1=p1->next;
        }while(p2&&p1!=p2);
        if(p2==NULL) return NULL;//没有环
        p2=pHead;
        p1=p1->next;
        while(p1!=p2){
            p1=p1->next;
            p2=p2->next;
        }
        return p1;
    }
};