Week 6: Linked Lists

1. Singly Linked List Fundamentals

A singly linked list is a chain of nodes where each node stores a value and a pointer to the next node — the last node's next is nullptr. Unlike a vector, nodes aren't stored contiguously in memory, so there's no way to jump to index i without walking the chain from the head.

linked_list.cpp

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int v) : val(v), next(nullptr) {}
};

// Build a list from a vector, returning a pointer to the head node.
// O(n) time, O(n) space for the n new nodes.
ListNode* buildList(const vector<int>& values) {
    ListNode dummy(0);       // dummy/sentinel node -- avoids special-casing the head
    ListNode* tail = &dummy;
    for (int v : values) {
        tail->next = new ListNode(v);
        tail = tail->next;
    }
    return dummy.next;
}

// Traverse and print -- O(n) time, O(1) extra space
void printList(ListNode* head) {
    for (ListNode* curr = head; curr != nullptr; curr = curr->next) {
        cout << curr->val << (curr->next ? " -> " : "\n");
    }
}

// Free every node -- linked lists don't clean themselves up
void freeList(ListNode* head) {
    while (head != nullptr) {
        ListNode* next = head->next;
        delete head;
        head = next;
    }
}

The dummy node pattern in buildList is worth internalizing now — it's a placeholder node before the real head that lets you always write tail->next = ... without a special case for "is this the first insertion?" You'll reach for the same trick constantly when a problem asks you to build or modify a list in place.

A dummy head simplifies almost every list problem

Whenever a problem might delete or insert before the current head — "remove all nodes with value X," "insert into a sorted list" — start with ListNode dummy(0); dummy.next = head; and operate relative to dummy. It turns "is this the head?" edge cases into the same code path as every other node.

2. Reversing a Linked List

Reversing a singly linked list means every node's next pointer should end up pointing at what used to be its previous node. There are two standard approaches, and interviewers usually want to see both because they trade time for stack space differently.

reverse_list.cpp

// Iterative: O(n) time, O(1) extra space -- the default choice in production code
ListNode* reverseIterative(ListNode* head) {
    ListNode* prev = nullptr;
    ListNode* curr = head;
    while (curr != nullptr) {
        ListNode* next = curr->next;   // save before overwriting
        curr->next = prev;             // reverse the pointer
        prev = curr;                   // advance prev
        curr = next;                   // advance curr
    }
    return prev;   // prev is the new head
}

// Recursive: O(n) time, O(n) space for the call stack -- elegant but not free
ListNode* reverseRecursive(ListNode* head) {
    if (head == nullptr || head->next == nullptr) {
        return head;   // base case: empty list or single node is already "reversed"
    }
    ListNode* newHead = reverseRecursive(head->next);
    head->next->next = head;   // make the next node point back at this one
    head->next = nullptr;      // this node is now the tail
    return newHead;
}

Trace the iterative version on paper with three nodes before moving on — the order of those four lines inside the loop matters. Save next first, or you lose the rest of the list the moment you overwrite curr->next.

Say the space complexity out loud

The recursive version looks shorter and cleaner, but each call frame stays on the stack until the base case returns, so it costs O(n) space versus the iterative version's O(1) — for a list with 100,000 nodes that can blow the call stack. Default to iterative unless the problem specifically wants the recursive structure (e.g., reversing in groups of k).

3. Cycle Detection: Floyd's Tortoise and Hare

A linked list has a cycle if some node's next pointer eventually loops back to a node already visited, instead of terminating at nullptr. Floyd's algorithm detects this in O(n) time and O(1) space using two pointers that move through the list at different speeds.

cycle_detection.cpp

// Returns true if the list contains a cycle. O(n) time, O(1) space.
bool hasCycle(ListNode* head) {
    ListNode* slow = head;   // tortoise: moves 1 step at a time
    ListNode* fast = head;   // hare: moves 2 steps at a time

    while (fast != nullptr && fast->next != nullptr) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) return true;   // they met -- there's a cycle
    }
    return false;   // fast reached the end -- no cycle
}

// Returns the node where the cycle begins, or nullptr if there is none.
// Once slow and fast meet inside the cycle, resetting one pointer to head
// and advancing both one step at a time makes them meet exactly at the cycle's start.
ListNode* detectCycleStart(ListNode* head) {
    ListNode* slow = head;
    ListNode* fast = head;

    while (fast != nullptr && fast->next != nullptr) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) {
            ListNode* ptr = head;
            while (ptr != slow) {
                ptr = ptr->next;
                slow = slow->next;
            }
            return ptr;   // the cycle's entry node
        }
    }
    return nullptr;
}

Why must they meet if a cycle exists? Once the fast pointer enters the cycle, the gap between fast and slow shrinks by exactly one node every step (fast gains two, slow gains one), so on a finite cycle that gap must eventually hit zero — they can never permanently "skip past" each other on a graph where every step moves forward by a fixed amount.

Slow/fast pointers solve more than cycles

The same two-speed technique finds the middle of a list in one pass (when fast reaches the end, slow is at the midpoint) and detects duplicate numbers via "value as pointer" tricks. Recognize "one pointer moves twice as fast as another" as a pattern, not a cycle-only trick.

4. Doubly Linked Lists

A doubly linked list adds a prev pointer alongside next, letting you walk the list in either direction and delete a known node in O(1) time without needing a reference to its predecessor — something a singly linked list can't do without an O(n) scan to find that predecessor first.

doubly_linked_list.cpp

struct DListNode {
    int val;
    DListNode* prev;
    DListNode* next;
    DListNode(int v) : val(v), prev(nullptr), next(nullptr) {}
};

// Insert newNode immediately after node -- O(1) time given a pointer to node.
void insertAfter(DListNode* node, DListNode* newNode) {
    newNode->next = node->next;
    newNode->prev = node;
    if (node->next != nullptr) {
        node->next->prev = newNode;
    }
    node->next = newNode;
}

// Remove node from the list -- O(1) time given a pointer to node, no head
// search required, unlike a singly linked list.
void removeNode(DListNode* node) {
    if (node->prev != nullptr) node->prev->next = node->next;
    if (node->next != nullptr) node->next->prev = node->prev;
    delete node;
}

That O(1) deletion-given-a-pointer property is exactly why a doubly linked list backs the classic LRU cache design: combined with a hash map from key to node pointer, you can move any node to the front or evict the tail in O(1) time, something neither a plain array nor a singly linked list can offer.

The trade-off is memory, not just complexity

Every node in a doubly linked list carries an extra pointer, so it uses roughly 50% more memory per node than a singly linked list on a typical 64-bit system. Reach for it when you specifically need backward traversal or O(1) arbitrary deletion — not as a default replacement for a singly linked list.

5. Hands-on Exercise

Hands-on

Implement a `MyLinkedList` class from scratch

Build a doubly linked list-backed list class supporting index-based operations, the same design LeetCode's classic "Design Linked List" problem asks for.

Requirements:

Define a MyLinkedList class using a DListNode internally, with a dummy head and dummy tail sentinel to avoid special-casing empty-list operations.
Implement int get(int index) returning the value at index, or -1 if out of range, in O(min(index, n − index)) time by choosing to walk from whichever end is closer.
Implement void insertAtHead(int val) and void insertAtTail(int val), both O(1).
Implement void insertAtIndex(int index, int val) that inserts so the new node becomes the node currently at index; if index == size, append; if index is out of range, do nothing.
Implement void deleteAtIndex(int index) that removes the node at index if it exists, using removeNode-style O(1) unlinking once the node is found.
Write a test main that exercises every method, including inserting at index 0, at the end, and deleting the only remaining node.

Hint

Keep a running size field updated on every insert/delete so get and insertAtIndex can bounds-check in O(1) before walking anything. With dummy head and tail sentinels linked to each other in an empty list, every insert and delete becomes the same four-pointer-update code path regardless of position.

6. Knowledge Check

Four quick questions. Expand each to check your answer.

What problem does a dummy head node solve when building or modifying a linked list?

Without a dummy node, inserting or deleting the actual head requires special-case code, because there's no "previous node" pointer to update when the head itself changes. A dummy node placed before the real head means every node — including the first real one — has a predecessor, so insertion and deletion logic can treat every position identically.

Compare the time and space complexity of iterative versus recursive linked list reversal.

Both run in O(n) time, visiting each node once. They differ in space: the iterative version uses three pointer variables regardless of list length, so it's O(1) extra space, while the recursive version keeps one stack frame alive per node until the base case unwinds, making it O(n) space — a real risk of stack overflow on very long lists.

In Floyd's cycle detection, why is it guaranteed that the slow and fast pointers eventually meet if a cycle exists?

Once the fast pointer is inside the cycle, both pointers keep looping through the same finite set of nodes, and the distance between them (measured along the cycle) decreases by exactly one node each step, since fast advances two steps to slow's one. A gap that shrinks by one every step on a finite loop must eventually reach zero, which is the moment they occupy the same node.

Why can a doubly linked list delete a given node in O(1) time while a singly linked list generally cannot, even with a direct pointer to that node?

Deleting a node means updating its predecessor's next pointer to skip over it. A doubly linked list stores that predecessor directly on the node via prev, so the update is O(1); a singly linked list has no backward pointer, so finding the predecessor requires walking from the head, which is O(n) in the general case.