Linked List Cycle: Detecting Loops in Data Structures

The "Linked List Cycle" problem involves identifying whether a cycle exists in a singly linked list.

Problem Statement

Determine if a given singly linked list has a cycle in it. In a linked list with a cycle, a node's next pointer points to an earlier node, creating a loop.

Example

Consider a linked list where the next pointer of a node points back to a previous node, forming a loop. The challenge is to detect this loop.

Solution Approach - Floyd's Tortoise and Hare Algorithm

Breaking Down the Solution

• Two Pointers: Initialize two pointers, slow and fast. slow moves one step at a time, while fast moves two steps.
• Iterate Through List: Move through the list, with slow and fast progressing at their respective speeds.
• Detecting the Cycle: If there is a cycle, slow and fast will eventually meet at some node. If they do, return true.
• Termination Condition: If fast or fast.next becomes null, it means the list has no cycle, and we return false.

Conclusion

The Linked List Cycle problem is a fundamental concept in data structures, particularly in understanding linked lists. Floyd's Tortoise and Hare algorithm provides an efficient way to detect cycles, demonstrating the importance of pointer manipulation and two-pointer techniques in algorithm design.

Rust Solution

Rust's Option<Rc<RefCell<ListNode>>> (aliased Link) is what lets both pointers share and mutate the same nodes: Rc provides shared ownership and RefCell the interior mutability, so head.clone() is a cheap reference-count bump rather than a deep copy. Detecting the meeting point needs Rc::ptr_eq(s, f2) to compare the underlying allocations — plain == would compare val fields instead, unlike the TS version's slow === fast. Each hop reads next through f.borrow(), and while let Some(f) = fast together with the match arms that early-return false unwrap the Option links in place of the null checks the other solutions rely on.

Go Solution

Go's *ListNode raw pointers make slow == fast a direct identity comparison — no helper needed, unlike Rust's Rc::ptr_eq — because comparing two pointers asks whether they address the same node. The for fast != nil && fast.Next != nil guard reads almost exactly like the TS while, with nil standing in for null and no Option to unwrap along the way. Building the sample list uses composite literals with address-of, &ListNode{Val: 3}, and the garbage collector reclaims the nodes, so there is no ownership machinery wrapped around the traversal.