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;
}

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

// 辅助函数：释放链表内存
void deleteList(ListNode* head) {
    while (head != nullptr) {
        ListNode* temp = head;
        head = head->next;
        delete temp;
    }
}

/*
    哈希表

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

    时间复杂度：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 的值就是环长度的「整数倍」。
    证明如下：
        假设相遇点距环的起点的距离为 m，环的起点距头结点 head 的距离为 k - m，
        也就是说如果从 head 前进 k - m 步就能到达环起点。
        如果从相遇点继续前进 k - m 步，也恰好到达环起点。
        所以，快慢指针中的任一个重新指向 head，然后两个指针同速前进，
        k - m 步后一定会相遇，相遇之处就是环的起点。

    时间复杂度：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 (true) {
        while (fast != nullptr) {
            if (fast->next == nullptr || fast->next->next == nullptr) return nullptr;
            fast = fast->next->next;
            slow = slow->next;
            if (fast == slow) break;
        }

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

        return slow;
    }
};

/*
    思路同上
*/
class Solution_2 {
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;
    }
};

int main() {
    // 示例输入
    Solution solution;
    vector<int> nums = {3, 2, 0, -4};
    ListNode* head = createList(nums);
    printList(head);
    // 构造环
    ListNode* cycleHead = head->next;
    ListNode* tail = head;
    while (tail->next != nullptr) {
        tail = tail->next;
    }
    tail->next = cycleHead;

    // 检测是否有环及环的入口
    ListNode* result = solution.detectCycle(head);
    // 打印结果
    if (result != nullptr) {
        cout << "Node value: " << result->val << endl;
    } else {
        cout << "No cycle found" << endl;
    }

    // 释放内存
    deleteList(head);

    return 0;
}

Golang 代码

package main

import "fmt"

// 定义链表节点
type ListNode struct {
    Val  int
    Next *ListNode
}

// createLinkedList 创建链表
func createLinkedList(values []int, pos int) *ListNode {
	if len(values) == 0 {
		return nil
	}
	head := &ListNode{Val: values[0]}
	current := head
	for _, val := range values[1:] {
		current.Next = &ListNode{Val: val}
		current = current.Next
	}

	// 如果 pos 不为 -1，则创建环
	if pos >= 0 {
		tail := current
		current = head
		for i := 0; i < pos; i++ {
			current = current.Next
		}
		tail.Next = current
	}

	return head
}

// printLinkedList 打印链表
func printLinkedList(head *ListNode, hasCycle bool) string {
	if hasCycle {
		return "Cycle detected, cannot print the entire list"
	}

	var result []int
	for head != nil {
		result = append(result, head.Val)
		head = head.Next
	}
	return fmt.Sprintf("%v", result)
}

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

    时间复杂度：O(n)
    空间复杂度：O(n)
*/
func detectCycle_0(head *ListNode) *ListNode {
    mp := map[*ListNode]struct{}{}
    for head != nil {
        if _, ok := mp[head]; ok {
            return head
        }
        mp[head] = struct{}{}
        head = head.Next
    }
    
    return nil
}

/*
    基本思路：
        使用快慢指针，快指针每次走两步，慢指针每次走一步。
        若链表中存在环，它们一定会在环内相遇。当相遇后，再让一个指针从链表头开始走，
        另一个指针从相遇点开始走，它们再次相遇的地方就是环的入口。
    
    时间复杂度：O(n)
        其中 n 是链表节点的总数。
        在寻找环以及找到环入口的过程中，都只需要遍历链表一次。
    空间复杂度：O(1)
        只使用了固定的额外空间。 
*/
func detectCycle(head *ListNode) *ListNode {
    slow, fast := head, head
    for fast != nil && fast.Next != nil {
        fast = fast.Next.Next
        slow = slow.Next
        if fast == slow {
            for slow != head {
                slow = slow.Next
                head = head.Next
            }
            return slow
        }
    }
    
    return nil
}

// 思路同上
func detectCycle_2(head *ListNode) *ListNode {
    slow, fast := head, head
    for fast != nil && fast.Next != nil {
        fast = fast.Next.Next
        slow = slow.Next
        if fast == slow {
            break
        }
    }
    // fast 为空指针，说明没有环
    if fast == nil || fast.Next == nil {
        return nil
    }

    // 重新指向头结点
    fast = head
    // 快慢指针同步前进，相交点就是环起点
    for fast != slow {
        fast = fast.Next
        slow = slow.Next
    }

    return slow
}

func main() {
    // 测试用例
    testCases := []struct {
        values []int
        pos    int
    }{
        {
            values: []int{3,2,0,-4},
            pos:    1,
        },
        {
            values: []int{1,2},
            pos:    0,
        },
        {
            values: []int{1},
            pos:    -1,
        },
    }

    for i, tc := range testCases {
        head := createLinkedList(tc.values, tc.pos)
        cycleEntry := detectCycle(head)
        if cycleEntry != nil {
            fmt.Printf("Test Case %d, Input: head = %v, pos = %d\n", i+1, printLinkedList(head, true), tc.pos)
            fmt.Printf("Test Case %d, Output: %v, PASS\n", i+1, cycleEntry)
        } else {
            fmt.Printf("Test Case %d, Input: head = %v, pos = %d\n", i+1, printLinkedList(head, false), tc.pos)
            fmt.Printf("Test Case %d, Output: nil, PASS\n", i+1)
        }
    }
}