Linked Lists

Why this module exists

Linked lists are a fundamental data structure that appears constantly in interviews. They test pointer manipulation, in-place algorithms, and the ability to handle edge cases. Many linked list problems have elegant O(1) space solutions using clever pointer techniques.

This module covers:

1. Linked list basics and operations
2. Reversal techniques
3. Two-pointer patterns (fast/slow)
4. Merging lists
5. Building complex data structures (LRU Cache)

1) Linked List Basics

A singly linked list node has a value and a pointer to the next node:

type ListNode struct {
    Val  int
    Next *ListNode
}

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

Key properties:

• Sequential access only (no random access)
• O(1) insertion/deletion if you have the pointer
• O(n) search
• No contiguous memory needed

2) The Dummy Head Trick

Many linked list problems become easier with a dummy node:

func process(head *ListNode) *ListNode {
    dummy := &ListNode{Next: head}
    current := dummy

    // Process list...

    return dummy.Next  // Real head
}

def process(head):
    dummy = ListNode(0, head)
    current = dummy

    # Process list...

    return dummy.next  # Real head

Why? Eliminates special cases for modifying the head.

3) Reversing a Linked List

The classic pointer manipulation problem. Reverse in-place with O(1) space.

Before: 1 -> 2 -> 3 -> 4 -> None
After:  4 -> 3 -> 2 -> 1 -> None

Iterative approach:

func reverseList(head *ListNode) *ListNode {
    var prev *ListNode
    current := head

    for current != nil {
        next := current.Next  // Save next
        current.Next = prev   // Reverse pointer
        prev = current        // Move prev forward
        current = next        // Move current forward
    }

    return prev  // New head
}

def reverse_list(head):
    prev = None
    current = head

    while current:
        next_node = current.next  # Save next
        current.next = prev       # Reverse pointer
        prev = current            # Move prev forward
        current = next_node       # Move current forward

    return prev  # New head

Visual:

Step 1: prev=None, curr=1
        1 -> 2 -> 3
        ^

Step 2: prev=1, curr=2
        1 <- 1    2 -> 3
             ^

Step 3: prev=2, curr=3
        1 <- 2    3
                  ^

Step 4: prev=3, curr=None
        1 <- 2 <- 3
                  ^

4) Recursive Reversal

func reverseList(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }

    newHead := reverseList(head.Next)
    head.Next.Next = head  // Point next node back to current
    head.Next = nil        // Current now points to nothing

    return newHead
}

def reverse_list(head):
    if not head or not head.next:
        return head

    new_head = reverse_list(head.next)
    head.next.next = head  # Point next node back
    head.next = None       # Break forward link

    return new_head

Insight: After recursion, head.next is the last node of the reversed tail. Point it back to head.

5) Fast and Slow Pointers

A powerful technique where two pointers move at different speeds.

Finding the middle:

func middleNode(head *ListNode) *ListNode {
    slow, fast := head, head

    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
    }

    return slow  // Middle (or second middle if even length)
}

def middle_node(head):
    slow = fast = head

    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

    return slow

Why it works: When fast reaches the end, slow is at the middle.

6) Cycle Detection (Floyd's Algorithm)

Detect if a linked list has a cycle:

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  // They meet = cycle exists
        }
    }

    return false  // Fast reached end = no cycle
}

def has_cycle(head):
    slow = fast = head

    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

        if slow == fast:
            return True

    return False

Why it works: If there's a cycle, fast will eventually lap slow.

Finding cycle start:

func detectCycle(head *ListNode) *ListNode {
    slow, fast := head, head

    // Find meeting point
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next

        if slow == fast {
            // Reset slow to head, move both at same speed
            slow = head
            for slow != fast {
                slow = slow.Next
                fast = fast.Next
            }
            return slow  // Cycle start
        }
    }

    return nil  // No cycle
}

Mathematical insight: Distance from head to cycle start equals distance from meeting point to cycle start.

7) Merging Two Sorted Lists

Merge two sorted lists into one sorted list:

func mergeTwoLists(l1, l2 *ListNode) *ListNode {
    dummy := &ListNode{}
    current := dummy

    for l1 != nil && l2 != nil {
        if l1.Val <= l2.Val {
            current.Next = l1
            l1 = l1.Next
        } else {
            current.Next = l2
            l2 = l2.Next
        }
        current = current.Next
    }

    // Attach remaining nodes
    if l1 != nil {
        current.Next = l1
    } else {
        current.Next = l2
    }

    return dummy.Next
}

def merge_two_lists(l1, l2):
    dummy = ListNode()
    current = dummy

    while l1 and l2:
        if l1.val <= l2.val:
            current.next = l1
            l1 = l1.next
        else:
            current.next = l2
            l2 = l2.next
        current = current.next

    # Attach remaining
    current.next = l1 or l2

    return dummy.next

Complexity: O(n + m) time, O(1) space.

8) LRU Cache

Least Recently Used cache: O(1) get and put operations.

Key insight: Combine a hash map (O(1) lookup) with a doubly linked list (O(1) removal/insertion).

type LRUCache struct {
    capacity int
    cache    map[int]*DLLNode
    head     *DLLNode  // Most recent
    tail     *DLLNode  // Least recent
}

type DLLNode struct {
    key, val   int
    prev, next *DLLNode
}

func Constructor(capacity int) LRUCache {
    lru := LRUCache{
        capacity: capacity,
        cache:    make(map[int]*DLLNode),
        head:     &DLLNode{},
        tail:     &DLLNode{},
    }
    lru.head.next = lru.tail
    lru.tail.prev = lru.head
    return lru
}

func (lru *LRUCache) Get(key int) int {
    if node, exists := lru.cache[key]; exists {
        lru.moveToFront(node)
        return node.val
    }
    return -1
}

func (lru *LRUCache) Put(key, value int) {
    if node, exists := lru.cache[key]; exists {
        node.val = value
        lru.moveToFront(node)
        return
    }

    // Add new node
    node := &DLLNode{key: key, val: value}
    lru.cache[key] = node
    lru.addToFront(node)

    // Evict if over capacity
    if len(lru.cache) > lru.capacity {
        lru.removeLRU()
    }
}

func (lru *LRUCache) moveToFront(node *DLLNode) {
    lru.removeNode(node)
    lru.addToFront(node)
}

func (lru *LRUCache) removeNode(node *DLLNode) {
    node.prev.next = node.next
    node.next.prev = node.prev
}

func (lru *LRUCache) addToFront(node *DLLNode) {
    node.next = lru.head.next
    node.prev = lru.head
    lru.head.next.prev = node
    lru.head.next = node
}

func (lru *LRUCache) removeLRU() {
    lru := lru.tail.prev
    lru.removeNode(lru)
    delete(lru.cache, lru.key)
}

class DLLNode:
    def __init__(self, key=0, val=0):
        self.key = key
        self.val = val
        self.prev = None
        self.next = None

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.cache = {}  # key -> node
        self.head = DLLNode()  # Dummy head (most recent)
        self.tail = DLLNode()  # Dummy tail (least recent)
        self.head.next = self.tail
        self.tail.prev = self.head

    def get(self, key):
        if key in self.cache:
            node = self.cache[key]
            self._move_to_front(node)
            return node.val
        return -1

    def put(self, key, value):
        if key in self.cache:
            node = self.cache[key]
            node.val = value
            self._move_to_front(node)
            return

        # Add new node
        node = DLLNode(key, value)
        self.cache[key] = node
        self._add_to_front(node)

        # Evict if needed
        if len(self.cache) > self.capacity:
            self._remove_lru()

    def _move_to_front(self, node):
        self._remove_node(node)
        self._add_to_front(node)

    def _remove_node(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev

    def _add_to_front(self, node):
        node.next = self.head.next
        node.prev = self.head
        self.head.next.prev = node
        self.head.next = node

    def _remove_lru(self):
        lru = self.tail.prev
        self._remove_node(lru)
        del self.cache[lru.key]

Why doubly linked list? Need O(1) removal, which requires access to both neighbors.

9) Common Patterns Summary

10) Common Mistakes

• Losing pointers: Always save next before modifying
• Null checks: Always check node != nil before accessing node.Next
• Forgetting dummy: Creates edge case bugs for head operations
• Off-by-one in middle: For even-length lists, which middle do you want?
• DLL pointer order: Update all four pointers when inserting/removing

11) Complexity Analysis

*O(1) if you keep a tail pointer †O(n) to find predecessor; O(1) if you have it

Outcomes

After this module, you should be able to:

• Reverse a linked list iteratively and recursively
• Use fast/slow pointers to find middle and detect cycles
• Merge sorted lists in O(1) space
• Design an LRU cache with O(1) operations

Practice Set

1. Reverse Linked List (Easy) — Core pointer manipulation
2. Merge Two Sorted Lists (Easy) — Dummy head and iteration
3. Linked List Cycle (Easy) — Floyd's fast/slow algorithm
4. LRU Cache (Medium) — Hash map + doubly linked list

Start with Reverse to master pointer manipulation. Merge shows the dummy head pattern. Cycle Detection introduces fast/slow pointers. LRU Cache combines data structures for a real-world application.