leetcode142：环形链表II

题目链接

leetcode

题目描述

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改 链表。

C++ 代码

#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;

// 链表结点的定义
struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

// 辅助函数：创建链表
ListNode* createList(const vector<int>& nums) {
    ListNode* dummy = new ListNode(-1);
    ListNode* cur = dummy;
    for (int num : nums) {
        cur->next = new ListNode(num);
        cur = cur->next;
    }
    return dummy->next;
}

// 辅助函数：创建带环链表
ListNode* createList(const vector<int>& nums, int pos) {
    if (nums.empty()) return nullptr;

    vector<ListNode*> nodes;
    for (int val : nums) {
        nodes.push_back(new ListNode(val));
    }
    for (int i = 0; i < nums.size()-1; i++) {
        nodes[i]->next = nodes[i+1];
    }
    if (pos != -1) {
        nodes.back()->next = nodes[pos]; // 设置环
    }

    return nodes[0];
}

// 辅助函数：打印链表
void printList(ListNode* head) {
    while (head != nullptr) {
        cout << head->val;
        if (head->next != nullptr) cout << " -> ";
        head = head->next;
    }
    cout << endl;
}

/*
    哈希表
    遍历链表中每个节点，将它记录到哈希表。
    若遇到之前遍历过的节点，则说明链表中存在环，返回该节点。

    时间复杂度：O(n)
        其中 n 是链表中的结点数。
        最坏情况下，遍历每个结点一次。
    空间复杂度：O(n)
        最坏情况下，将每个结点插入到哈希表一次。
*/
class Solution_0 {
public:
    ListNode *detectCycle(ListNode *head) {
        unordered_set<ListNode*> visited;
        while (head != nullptr) {
            if (visited.count(head)) {
                return head;
            }
            visited.insert(head);
            head = head->next;
        }
        
        return nullptr;
    }
};

/*
    双指针
    
    假设快慢指针相遇时，慢指针 slow 走了 k 步，那么快指针 fast 一定走了 2k 步。
    多走的 k 步就是 fast 指针在环里转圈，所以 k 是环长度的「整数倍」。

    时间复杂度：O(n)
    空间复杂度：O(1)
*/
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if (head == nullptr || head->next == nullptr) {
            return nullptr;
        }

        ListNode *fast = head, *slow = head;
        while (fast != nullptr && fast->next != nullptr) {
            fast = fast->next->next;
            slow = slow->next;
            if (fast == slow) {
                break;
            }
        }
        // 若 fast 为空指针，则说明没有环
        if (fast == nullptr || fast->next == nullptr) {
            return nullptr;
        }

        // 重新指向头结点
        fast = head;
        // 快慢指针同步前进，相交点就是入环的第一个节点
        while (fast != slow) {
            fast = fast->next;
            slow = slow->next;
        }

        return slow;
    }
};

// 辅助函数：打印数组
void printArray(const vector<int>& nums) {
    cout << "[";
    for (size_t i = 0; i < nums.size(); i++) {
        cout << nums[i];
        if (i != nums.size() - 1) cout << ",";
    }
    cout << "]";
}

int getIndex(const vector<int>& nums, int value) {
    for (size_t i = 0; i < nums.size(); i++) {
        if (nums[i] == value) {
            return i;
        }
    }
    return -1;
}

int main() {
    Solution solution;
    vector<vector<int>> head_cases = {
        {3,2,0,-4},
        {1,2},
        {1}
    };
    vector<int> pos_cases = {
        1, 0, -1
    };

    for (size_t i = 0; i < head_cases.size(); i++) {
        auto& nums = head_cases[i];
        int pos = pos_cases[i];
        ListNode* head = createList(nums, pos);

        cout << "Input: head = ";
        printArray(nums);
        cout << ", pos = " << pos << endl;
        
        // 检测是否有环及环的入口
        ListNode* result = solution.detectCycle(head);
        if (result != nullptr) {
            int index = getIndex(nums, result->val);
            cout << "Output: " << index << endl;
        } else {
            cout << "Output: null " << endl;
        }
    }

    return 0;
}