leetcode141：环形链表

题目链接

leetcode

题目描述

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

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:
    bool hasCycle(ListNode *head) {
        unordered_set<ListNode*> set;
        while (head != nullptr) {
            if (set.count(head)) {
                return true;
            }
            set.insert(head);
            head = head->next;
        }

        return false;
    }
};

/*
    双指针

    两个指针从头开始扫描，第一个指针每次走一步，第二个指针每次走两步。
    如果走到 null，说明不存在环；否则，说明存在环。
    为什么呢？假设链表存在环
    当第一个指针走到环入口时，第二个指针已经走到环上的某个位置，距离环入口还差 x 步。
    由于第二个指针比第一个指针每次多走一步，所以第一个指针再走 x 步，两个指针就相遇了。

    时间复杂度：O(n)
        其中 n 是链表中的结点数。
        第一个指针在环上走不到一圈，所以第一个指针走的总步数小于链表总长度。
        第二个指针走的步数是第一个指针的两倍，所以总时间复杂度是 O(n)。
    空间复杂度：O(1)
        只使用了两个指针变量的额外空间。
*/
class Solution {
public:
    bool hasCycle(ListNode *head) {
        if (head == nullptr || head->next == nullptr) return false;

        ListNode *slow = head, *fast = head;
        // 快指针走到末尾时停止
        while (fast != nullptr && fast->next != nullptr) {
            // 慢指针走一步，快指针走两步
            slow = slow->next;
            fast = fast->next->next;
            // 快慢指针相遇，说明含有环
            if (slow == fast) {
                return true;
            }
        }
        // 不包含环
        return false;
    }
};

/*
    思路同上
*/
class Solution_2 {
public:
    bool hasCycle(ListNode *head) {
        if (head == nullptr || head->next == nullptr) return false;

        ListNode *slow = head, *fast = head->next;
        while (slow != fast) {
            if (fast == nullptr || fast->next == nullptr) {
                return false;
            }
            slow = slow->next;
            fast = fast->next->next;
        }

        return true;
    }
};

int main() {
    // 示例输入
    Solution solution;
    vector<int> nums = {3, 2, 0, -4};

    ListNode* head = createList(nums);
    ListNode* tail = head;
    // 创建环形链表
    for (int i = 0; i < nums.size(); ++i) {
        if (i > 0) {
            tail->next = head;
        }
        tail = tail->next;
    }

    // 检测是否有环
    bool result = solution.hasCycle(head);
    // 打印结果
    cout << "Result: " << (result ? "true" : "false") << 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
}

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)
        其中 n 是链表中的结点数。
        最坏情况下，遍历每个结点一次。
    空间复杂度：O(n)
        最坏情况下，将每个结点插入到哈希表中一次。
*/
func hasCycle_0(head *ListNode) bool {
    mp := map[*ListNode]struct{}{}
    for head != nil {
        if _, ok := mp[head]; ok {
            return true
        }
        mp[head] = struct{}{}
        head = head.Next
    }

    return false
}

/*
    基本思路：
        使用快慢指针，慢指针每次移动一步，快指针每次移动两步。
        若链表有环，则快指针一定会在某个时刻追上慢指针；
        若链表无环，则快指针最终会到达链表尾部。
    
    时间复杂度：O(n)
        其中 n 是链表的长度。
        有环的情况下，快指针最多比慢指针多跑一圈就会相遇；
        在无环的情况下，遍历完整个链表，与链表长度线性相关。
    空间复杂度：O(1)
        只使用了固定的几个额外变量。
*/
func hasCycle(head *ListNode) bool {
    slow, fast := head, head
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
        if slow == fast {
            return true
        }
    }

    return false
}

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

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