题目描述 牛客网

• 如果一个链表中包含环，如何找出环的入口节点？

• 例如，在如下图所示的链表中，环的入口节点是节点3

题目解读

• 剑指Offer 139
• 书上思路挺想详细的，请自行翻阅
• 第一步：确定一个链表中是否包含环。受到面试题22的启发，我们可以用两个指针来解决这个问题。和前面问题一样，定义两个指针，同时从链表的头节点出发，一个指针一次走一步，另一个指针一次走两步。如果走得快的指针追上了走得慢的指针，那么链表就包含环；如果走得快的指针走到了链表的末尾都没有追上第一个指针，那么链表就不包含环
• 第二步：得到环中节点数目。我们在前面提到判断一个链表里是否有环时用到了一快一慢指针。如果两个指针相遇，则表明链表中存在环。两个指针相遇的节点一定是在环中。可以从这个节点出发，一边继续向前移动一边计数，当再次回到这个节点时，就可以得到环中节点数了
• 第三步：找到环的入口。我们还是可以用两个指针来解决这个问题。先定义两个指针 p1 、p2 指向链表的头节点。如果链表中的环有 n 个节点，则指针 p1 先在链表上向前移动 n 步，然后两个指针以相同的速度向前移动。当第二个指针指向环的入口节点时，第一个指针已经围绕着环走了一圈，又回到了入口节点

代码

• 第一轮代码

#include<iostream>
using namespace std;

struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};

class Solution {
public:
    // 找到环中共有多少个节点
    // 此处注意必须注意编写代码时要考虑指针为空的情况，要不然程序太不健壮了.. 
    int find_loop_sum(ListNode* pHead){
        int n = 0;
        ListNode *kuai = NULL;
        ListNode *man  = NULL;

        if(pHead->next){
            man = pHead -> next;
        }else{
            return 0;
        }

        if(man->next){
            kuai = man -> next;
        }else{
            return 0;
        }

        while(kuai != man){
            if(kuai->next && kuai->next->next){
                kuai = kuai -> next -> next;
                man  = man  -> next; 
            }else{
                return 0;
            }
        }

        // 代码运行到这里的时候，kuai man 指针指向同一个节点且均在环中，
        // 此时，让一个指针在原地等待，一个在环中跑一圈，当另一个指针再次回到原点时，则遍历完环中节点数目
        while(kuai -> next != man){
            kuai = kuai -> next;
            n++;
        }
        n++;

        cout<<n<<endl;

        return n;
    }

    ListNode* EntryNodeOfLoop(ListNode* pHead)
    {
        if(!pHead){
            return NULL;
        }

        int n = find_loop_sum(pHead);

        if(n == 0){
            return NULL;
        }

        ListNode *p1 = pHead;
        ListNode *p2 = pHead;

        for(int i=0; i < n; i++){
            p1 = p1 -> next;
        }

        while(p1 != p2){
            p1 = p1 -> next;
            p2 = p2 -> next;
        }
        return p1;
    }


    ListNode* create(){
        ListNode *p;
        ListNode *head = NULL;
        ListNode *tail = NULL;
        ListNode *loop = NULL;

        for(int i=1; i <= 6; i++){
            p = new ListNode(i);

            if(i == 3){
                loop = p;
            }

            if(!head){
                head = p;
            }
            else{
                tail -> next = p;
            }
            tail = p;
        }
        tail -> next = loop;

        return head;
    }

    void print_Node(ListNode *head){
        for(int i = 1; i <= 10; i++){
            cout<<head->val<<" ";
            head = head->next;
        }
        cout<<endl;
    }
};

main(){
    Solution ss;
    ListNode *head = NULL;
    ListNode *loop = NULL;

    head = ss.create();
    ss.print_Node(head);
    // cout<<ss.find_loop_sum(head)<<endl;
    loop = ss.EntryNodeOfLoop(head);
    cout<<loop->val<<endl;
}

• 第二轮代码

class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead){
        if(pHead == NULL){
            return NULL;
        }
        
        // 找到环中节点数目
        int count = find_loop_count(pHead);
        if(count == 0){
            return NULL;
        }
        
        // 找到环的入口
        ListNode* p1 = pHead;
        ListNode* p2  = pHead;
        for(int i=0; i < count; i++){
            p1 = p1->next;
        }
        
        while(p1 != p2){
            p1 = p1->next;
            p2 = p2->next;
        }
        return p1;
    }
    
    // 找到环中节点数目
    int find_loop_count(ListNode* pHead){
        ListNode* kuai = NULL;
        ListNode* man  = NULL;
        
        // 第一步先判断是否有环
        if(pHead->next != NULL && pHead->next->next != NULL){
            man = pHead->next;
            kuai = pHead->next->next;
        }else{
            return 0;
        }
        while(kuai != man){
            if(kuai->next->next != NULL && man->next != NULL){
                kuai = kuai->next->next;
                man  = man->next;
            }else{
                return 0;
            }
        }
        
        // 找到环中数目
        int count = 0;
        while(kuai->next != man){
            kuai = kuai->next;
            count++;
        }
        count++;
        return count;
    }
};

2023.5.25 第三轮

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
#include <cstddef>
class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead) {
        if (!pHead) return pHead;
        int n = GetLoopCount(pHead);
        std::cout << "n = " << n << std::endl;
        if (n == 0) return NULL;

        ListNode* p1 = pHead;
        ListNode* p2 = pHead;
        for (int i=0; i<n; i++) {
            p1 = p1->next;
        }
        while (p1 != p2) {
            p1 = p1->next;
            p2 = p2->next;
        }
        return p1;
    }
    int GetLoopCount(ListNode* pHead) {
        int n = 0;
        bool flag = false;
        // 1、一快一慢两个指针先判断是否有环
        ListNode* kuai = pHead;
        ListNode* man = pHead;
        while (kuai->next && kuai->next->next) {
            kuai = kuai->next->next;
            man = man->next;
            if (kuai == man) {
                flag = true;
                break;
            }
        }
        if (flag) {
            kuai = kuai->next;
            while (kuai != man) {
                kuai = kuai->next;
                n++;
            }
            n++;
        }
        return n;
    }
};

总结展望

• 越来越发现剑指 offer 题目是真好，自己见识还是太浅显
• 认真，努力，勤奋