剑指offer JZ23链表中环的入口节点 C++

news/2024/7/3 7:37:45

1、题目描述

在这里插入图片描述

2、在VS2019上运行

#include <iostream>

using namespace std;

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

class Solution {
public:
    // 判断链表是否有环，返回相遇的地方
    ListNode* hasCycle(ListNode* head) {
        if (head == 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)
                return slow;
        }

        return NULL;
    }

    // 返回环形链表入口节点
    ListNode* EntryNodeOfLoop(ListNode* head) {
        ListNode* slow = hasCycle(head);
        if (slow == NULL)
            return NULL;

        ListNode* fast = head;

        while (fast != slow) {
            fast = fast->next;
            slow = slow->next;
        }

        return slow;
    }
};

// 主函数
int main() {
    ListNode* node1 = new ListNode(1);
    ListNode* node2 = new ListNode(2);
    ListNode* node3 = new ListNode(3);
    ListNode* node4 = new ListNode(4);
    ListNode* node5 = new ListNode(5);

    node1->next = node2;
    node2->next = node3;
    node3->next = node4;
    node4->next = node5;
    node5->next = node3; // 构造环

    Solution solution;
    ListNode* entry = solution.EntryNodeOfLoop(node1);
    if (entry != NULL)
        cout << entry->val << endl; // 输出环的入口节点值
    else
        cout << "No cycle" << endl;

    return 0;
}

运行结果：3

3、判断链表中是否有环

1、链表不像二叉树，链表每个节点只有一个val值和一个next指针，也就是说一个节点只能有一个指针指向下一个节点，不能有两个指针，那么这时就可以说一个性质：环形链表的环一定在末尾，末尾没有NULL了。
2、如果是普通的线形链表末尾一定有NULL，那么就可以根据链表中是否有NULL判断是不是有环。
3、使用双指针，同向访问的快慢指针，因为有速度差异，二者一定会相遇。
-4、具体做法：
step1:设置快慢两个指针，初始都指向链表头。
step2：遍历链表，快指针每次走两步，慢指针每次走一步。
step3:如果快指针到了链表末尾，说明没有环，因为它每次走两步，所以要验证连续两步是否为NULL
step4:如果链表有环，那快慢指针会在环内循环，因为快指针每次走两步，因此快指针会在环内追到慢指针，二者相遇就代表有环。