环形链表

• 题目要求
• 解题思路
• Golang 版本
• C++版本
• Python 版本
• Java 版本
• Rust 版本
• 总结

题目要求

这个问题要求我们检测一个单向链表是否包含一个环。一个链表环指的是链表中的一个节点的next指针指向的是链表中在它之前的某个节点，这样就形成了一个环。这意味着如果我们从头节点开始遍历链表，我们会因为环的存在而无法到达链表的尾部（因为它没有真正的尾部）。我们的任务是要编写一个算法，来检测链表是否包含这样的环。

解题思路

要解决这个问题，有几种不同的算法可以使用。以下是两种常见的方法：

1. 哈希表法：

   • 遍历链表的每个节点。
   • 对于每个节点，检查它是否已经在一个哈希表（或者任何其他类型的数据结构）中。
   • 如果当前节点已经出现在哈希表中，那么链表包含一个环。
   • 如果遍历完整个链表都没有发现重复的节点，那么链表不包含环。
   • 这种方法的时间复杂度是 O(n)，空间复杂度也是 O(n)，因为我们需要存储每个节点来检查是否有重复。

2. 快慢指针法（Floyd 的循环检测算法）：

   • 使用两个指针，一个快指针和一个慢指针，初始时都指向头节点。
   • 快指针每次移动两个节点，慢指针每次移动一个节点。
   • 如果链表不包含环，快指针将到达链表的尾部并且遍历结束。
   • 如果链表包含环，快指针最终会追上慢指针（因为每次循环它都比慢指针多走一步）。
   • 当快指针与慢指针相遇时，我们可以确定链表包含一个环。
   • 这种方法的时间复杂度是 O(n)，但空间复杂度优于哈希表法，为 O(1)，因为它不需要额外的存储空间。

通常，快慢指针法更受欢迎，因为它不需要额外的存储空间，而且实现起来相对简单。

Golang 版本

package main

import "fmt"

// ListNode is the definition for singly-linked list.
type ListNode struct {
    Val  int
    Next *ListNode
}

// hasCycle uses Floyd's Tortoise and Hare algorithm to detect a cycle.
func hasCycle(head *ListNode) bool {
    if head == nil || head.Next == nil {
        return false
    }

    slow := head
    fast := head.Next

    for fast != nil && fast.Next != nil {
        if slow == fast {
            return true
        }
        slow = slow.Next
        fast = fast.Next.Next
    }

    return false
}

func main() {
    // Example usage:
    // Create a list with a cycle for testing purposes.
    // 1 -> 2 -> 3 -> 4 -> 2 ...

    node4 := &ListNode{Val: 4}
    node3 := &ListNode{Val: 3, Next: node4}
    node2 := &ListNode{Val: 2, Next: node3}
    node1 := &ListNode{Val: 1, Next: node2}
    node4.Next = node2 // Create a cycle here

    fmt.Println(hasCycle(node1)) // Should return true
}

这段代码定义了一个ListNode结构体，代表链表的节点，并实现了hasCycle函数来检测链表是否有环。hasCycle函数使用了快慢指针法。在main函数中，我们创建了一个带有环的链表作为示例，并调用hasCycle函数来检测环。

C++版本

#include <iostream>

// Definition for singly-linked list.
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

class Solution {
public:
    bool hasCycle(ListNode *head) {
        if (head == nullptr || head->next == nullptr) {
            return false;
        }

        ListNode *slow = head;
        ListNode *fast = head->next;

        while (fast != nullptr && fast->next != nullptr) {
            if (slow == fast) {
                return true;
            }
            slow = slow->next;
            fast = fast->next->next;
        }

        return false;
    }
};

int main() {
    // Example usage:
    // Create a list with a cycle for testing purposes.
    // 1 -> 2 -> 3 -> 4 -> 2 ...

    ListNode *node1 = new ListNode(1);
    ListNode *node2 = new ListNode(2);
    ListNode *node3 = new ListNode(3);
    ListNode *node4 = new ListNode(4);

    node1->next = node2;
    node2->next = node3;
    node3->next = node4;
    node4->next = node2; // Create a cycle here

    Solution solution;
    std::cout << "Does the linked list have a cycle? "
              << (solution.hasCycle(node1) ? "Yes" : "No") << std::endl;

    // Remember to avoid memory leak in production code.
    // Here we would need to properly delete nodes, especially since we have a cycle.
    // For this example, we'll skip this part.

    return 0;
}

这段 C++代码定义了一个ListNode结构体，代表链表的节点，并实现了一个Solution类，其中包含了hasCycle函数来检测链表是否有环。hasCycle函数使用了快慢指针法。在main函数中，我们创建了一个带有环的链表作为示例，并调用hasCycle函数来检测环。最后，输出检测结果。

请注意，在实际的生产代码中，你需要确保没有内存泄漏。在这个例子中，由于链表中存在环，如果你想删除所有节点，你需要特别小心。这里为了简单起见，我们没有包含删除节点的代码。

Python 版本

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def hasCycle(self, head):
        if not head or not head.next:
            return False

        slow = head
        fast = head.next

        while fast and fast.next:
            if slow == fast:
                return True
            slow = slow.next
            fast = fast.next.next

        return False

# Example usage:
# Create a list with a cycle for testing purposes.
# 1 -> 2 -> 3 -> 4 -> 2 ...

node1 = ListNode(1)
node2 = ListNode(2)
node3 = ListNode(3)
node4 = ListNode(4)

node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node2  # Create a cycle here

solution = Solution()
print("Does the linked list have a cycle?", solution.hasCycle(node1))  # Should return True

这段 Python 代码定义了一个ListNode类，代表链表的节点，并实现了一个Solution类，其中包含了hasCycle方法来检测链表是否有环。hasCycle方法使用了快慢指针法。在示例使用中，我们创建了一个带有环的链表，并调用hasCycle方法来检测环，然后打印出检测结果。

Java 版本

public class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
        next = null;
    }
}

public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) {
            return false;
        }

        ListNode slow = head;
        ListNode fast = head.next;

        while (fast != null && fast.next != null) {
            if (slow == fast) {
                return true;
            }
            slow = slow.next;
            fast = fast.next.next;
        }

        return false;
    }
}

public class Main {
    public static void main(String[] args) {
        // Example usage:
        // Create a list with a cycle for testing purposes.
        // 1 -> 2 -> 3 -> 4 -> 2 ...

        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);

        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node2; // Create a cycle here

        Solution solution = new Solution();
        System.out.println("Does the linked list have a cycle? " + solution.hasCycle(node1)); // Should return true
    }
}

这段 Java 代码定义了一个ListNode类，代表链表的节点，并实现了一个Solution类，其中包含了hasCycle方法来检测链表是否有环。hasCycle方法使用了快慢指针法。在Main类的main方法中，我们创建了一个带有环的链表作为示例，并调用hasCycle方法来检测环，然后打印出检测结果。

Rust 版本

use std::rc::Rc;
use std::cell::RefCell;

// Definition for singly-linked list.
#[derive(Clone)]
struct ListNode {
    val: i32,
    next: Option<Rc<RefCell<ListNode>>>,
}

impl ListNode {
    fn new(val: i32) -> Self {
        ListNode { val, next: None }
    }
}

struct Solution;

impl Solution {
    pub fn has_cycle(head: Option<Rc<RefCell<ListNode>>>) -> bool {
        let mut slow = head.clone();
        let mut fast = head;

        while let Some(fast_node) = fast {
            if let Some(next_fast) = fast_node.borrow().next.clone() {
                fast = next_fast.borrow().next.clone();
                slow = slow.unwrap().borrow().next.clone();

                if Rc::ptr_eq(&slow.as_ref().unwrap(), &fast.as_ref().unwrap()) {
                    return true;
                }
            } else {
                break;
            }
        }

        false
    }
}

fn main() {
    // Example usage:
    // Create a list with a cycle for testing purposes.
    // 1 -> 2 -> 3 -> 4 -> 2 ...

    let node4 = Rc::new(RefCell::new(ListNode::new(4)));
    let node3 = Rc::new(RefCell::new(ListNode::new(3)));
    let node2 = Rc::new(RefCell::new(ListNode::new(2)));
    let node1 = Rc::new(RefCell::new(ListNode::new(1)));

    node1.borrow_mut().next = Some(node2.clone());
    node2.borrow_mut().next = Some(node3.clone());
    node3.borrow_mut().next = Some(node4.clone());
    node4.borrow_mut().next = Some(node2.clone()); // Create a cycle here

    println!("Does the linked list have a cycle? {}", Solution::has_cycle(Some(node1))); // Should return true
}

这段 Rust 代码定义了一个ListNode结构体，代表链表的节点，并实现了一个Solution结构体，其中包含了has_cycle函数来检测链表是否有环。has_cycle函数使用了快慢指针法。在main函数中，我们创建了一个带有环的链表作为示例，并调用has_cycle函数来检测环，然后打印出检测结果。

Rust 中的链表实现通常涉及到智能指针和借用检查器，这里使用了Rc和RefCell来允许节点被多个所有者共享，并在运行时借用其可变性。这是因为在 Rust 中，我们通常不能在编译时确定链表的生命周期和所有权模式。

总结

上面给出了使用不同编程语言实现的检测链表是否包含环的算法。这些算法主要包括了哈希表法和快慢指针法两种解决方案。

• 哈希表法：遍历链表的每个节点，检查每个节点是否已经在哈希表中。这种方法的时间复杂度是 O(n)，空间复杂度也是 O(n)。
• 快慢指针法：使用两个指针，一个快指针和一个慢指针，通过不同的移动速度来检测环的存在。这种方法的时间复杂度是 O(n)，但空间复杂度优于哈希表法，为 O(1)。

这些算法可以根据具体的编程语言特性进行实现。在实际应用中，快慢指针法通常更受欢迎，因为它不需要额外的存储空间，而且实现起来相对简单。