Visualization Exercise: Pointer Traversal

Mastering linked lists requires developing strong visual intuition for pointer manipulations without losing references or causing memory leaks.

Challenge 1: In-Place Linked List Reversal

The Problem

Given the head of a singly linked list, reverse the list in-place in O(n) time and O(1) auxiliary memory space.

Copy codeInput:  [ 1 ] ---> [ 2 ] ---> [ 3 ] ---> [ 4 ] ---> null
Output: [ 4 ] ---> [ 3 ] ---> [ 2 ] ---> [ 1 ] ---> null

The Three-Pointer Technique

To reverse a link curr -> curr.next, you must point curr.next backward to prev. But if you do that immediately, you lose reference to the rest of the list! Therefore, you need three pointers: prev, curr, and nextTemp.

Copy codeStep 1: Save next:       nextTemp = curr.next
Step 2: Reverse pointer: curr.next = prev
Step 3: Advance prev:    prev = curr
Step 4: Advance curr:    curr = nextTemp

Copy codefun <T> reverseList(head: Node<T>?): Node<T>? {
    var prev: Node<T>? = null
    var curr: Node<T>? = head

    while (curr != null) {
        val nextTemp = curr.next // 1. Save remaining chain
        curr.next = prev         // 2. Reverse link
        prev = curr              // 3. Move prev forward
        curr = nextTemp          // 4. Move curr forward
    }
    return prev // 'prev' is the new head!
}

Challenge 2: Cycle Detection (Floyd's Tortoise and Hare)

The Problem

Determine whether a linked list contains a cycle (loop) where a node points back to an earlier node, which would cause an infinite loop during standard traversal.

Copy code[ 1 ] ---> [ 2 ] ---> [ 3 ] ---> [ 4 ]
                   ^               |
                   |               v
                   +------------- [ 5 ]

The Fast & Slow Pointer Algorithm

1. Initialize two pointers: slow = head, fast = head.
2. Move slow by 1 step per iteration.
3. Move fast by 2 steps per iteration.
4. If there is no cycle, fast will reach null.
5. If there is a cycle, fast will eventually lap and collide with slow (slow == fast).

Copy codefun hasCycle(head: Node<Int>?): Boolean {
    var slow = head
    var fast = head

    while (fast?.next != null) {
        slow = slow?.next
        fast = fast.next?.next

        if (slow == fast) {
            return true // Cycle detected!
        }
    }
    return false // Reached end of list -> No cycle
}

Complexity:

• Time Complexity: O(n)
• Space Complexity: O(1) (no HashSet needed!)

Summary

• Pointer rewiring always requires temporary variables to avoid dropping the remainder of the list.
• In-place reversal is achieved using three pointers: prev, curr, and nextTemp.
• Two-pointer techniques (fast & slow) solve cycle detection and midpoint finding in O(n) time and O(1) memory.