Linked Lists | Phase 2

Structure of a Linked List

A linked list is a chain of nodes. Each node has a value and a pointer to the next node. Unlike arrays, nodes are NOT contiguous in memory.

head ↓

→

nullptr

Access node 7 (index 1): must traverse from head → O(n). No direct jumping.

Node Definition & Basic Operations

C++
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

// Build: 1 → 2 → 3 → nullptr
ListNode* head = new ListNode(1);
head->next     = new ListNode(2);
head->next->next = new ListNode(3);

// Traverse
ListNode* cur = head;
while (cur) {
    cout << cur->val << " ";
    cur = cur->next;
}

// Insert after node p — O(1)
void insertAfter(ListNode* p, int val) {
    ListNode* node = new ListNode(val);
    node->next = p->next;
    p->next = node;
}

// Delete node after p — O(1)
void deleteAfter(ListNode* p) {
    ListNode* tmp = p->next;
    p->next = p->next->next;
    delete tmp;
}
    

Complexity: Array vs Linked List

Operation	Array	Linked List	Why
Access by index	O(1)	O(n)	LL traverses from head
Search	O(n)	O(n)	Both must scan
Insert at head	O(n)	O(1)	LL: just update pointer
Insert at tail	O(1)*	O(1)**	**With tail pointer
Insert at index	O(n)	O(n)	LL: O(n) find + O(1) link
Delete at head	O(n)	O(1)	LL advantage

4 Core Techniques

1. Dummy Head Node

Create a dummy node before head. Avoids special-casing when operations might affect the real head. Return dummy.next at end.

2. Fast & Slow Pointers

slow moves 1 step, fast moves 2. When fast reaches end → slow is at middle. If fast meets slow → cycle exists.

3. Reverse In-Place

prev=nullptr, cur=head. Each step: save next, point cur to prev, advance both. Classic O(n), O(1).

4. Two-Pass Technique

First pass: measure length or find a node. Second pass: process using info from first. Nth from end in O(n).

Reverse a Linked List — The Most Important Pattern

C++
ListNode* reverseList(ListNode* head) {
    ListNode* prev = nullptr;
    ListNode* cur  = head;
    while (cur) {
        ListNode* nxt = cur->next;  // save next
        cur->next = prev;           // reverse link
        prev = cur;                 // advance prev
        cur  = nxt;                 // advance cur
    }
    return prev;   // new head
}
// Trace: 1→2→3→nullptr
// After: nullptr←1←2←3   return 3
// Time: O(n)  Space: O(1)
    

Interactive: Reverse a Linked List

Watch the 3-pointer dance: save next, redirect cur→prev, advance both pointers. O(n) time, O(1) space.

Interactive: Floyd's Cycle Detection

Slow moves 1 step, fast moves 2. If there's a cycle they must meet. Watch node 6 loop back to node 3.

Deeper Understanding

🧠 Under the Hood

Each node is allocated independently on the heap. The "next" field stores a raw memory address pointing to the next node — which could be anywhere in RAM. This is why linked list traversal is slow compared to arrays: every step causes a cache miss, fetching a new cache line. A sequential scan over a 1000-node list touches ~1000 different cache lines vs ~16 for an array.

⚖️ When to Use / When NOT to Use

✅ Use when you need O(1) insertion/deletion at a known node

Splice in/out without shifting — just redirect a pointer. Perfect for LRU cache, task queues with mid-removal.

✅ Use when size is highly variable and insertions interleave with deletions

No expensive realloc/copy. std::list never moves existing elements.

❌ Avoid when you need random access by index

Instead: vector. Linked list index access is O(n) — must walk from head.

❌ Avoid when you just need a fast dynamic array

Instead: vector. In practice, cache effects make vector 5–10× faster than list even for insert/delete in many workloads.

🚫 Common Misconceptions

❌ "Linked lists are faster because insert is O(1)"

Finding the node to insert at is O(n). The O(1) insert only applies when you already hold a pointer to that node. In practice, you almost never do.

❌ "You always need two passes to find the middle"

One pass with fast/slow pointers: slow advances 1 step per iteration, fast 2 steps. When fast reaches the end, slow is at the middle.

❌ "Reversing a LL requires O(n) space"

In-place reversal needs only 3 pointers (prev, cur, next). O(1) extra space. The common mistake is using a stack or storing all nodes.

🎤 Interview Follow-ups

Q: What's the dummy head trick and why use it?

A dummy (sentinel) node before head eliminates special-casing for head modifications. Result is always dummy.next — cleaner code with no edge case for empty-list or first-node changes.

Q: Why does fast/slow find the cycle start? (math)

At meeting point M, slow traveled d+m steps, fast traveled d+m+k·C (k full cycles). Since fast=2·slow: d+m+k·C = 2(d+m) → d = k·C−m. Resetting one pointer to head and stepping both 1/step lands them at the cycle start.

Q: Array vs list cache behavior?

Array: n elements → ⌈n·sizeof(T)/64⌉ cache lines fetched. List: n nodes → up to n cache lines (one per node). For n=1000 ints, array uses ~16 lines; list uses ~1000. Arrays win on sequential access.

Practice Problems

#206Reverse Linked ListEasy

Reverse a singly linked list. 1→2→3→4→5 becomes 5→4→3→2→1.

Pattern: Three-pointer reversal. prev=nullptr, cur=head. Each iteration: save next, flip pointer, advance.

C++
ListNode* reverseList(ListNode* head) {
    ListNode *prev = nullptr, *cur = head;
    while (cur) {
        ListNode* nxt = cur->next;
        cur->next = prev;
        prev = cur; cur = nxt;
    }
    return prev;
}
// Time: O(n)  Space: O(1)

#21Merge Two Sorted ListsEasy

Merge two sorted linked lists into one sorted list in-place.

Pattern: Dummy head. Compare front of both lists, attach smaller, advance that pointer.

C++
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    ListNode dummy(0);
    ListNode* cur = &dummy;
    while (l1 && l2) {
        if (l1->val <= l2->val) { cur->next = l1; l1 = l1->next; }
        else                     { cur->next = l2; l2 = l2->next; }
        cur = cur->next;
    }
    cur->next = l1 ? l1 : l2;
    return dummy.next;
}
// Time: O(m+n)  Space: O(1)

#141Linked List CycleEasy

Detect if linked list has a cycle. O(1) space required.

Pattern: Floyd's Cycle Detection. Fast moves 2 steps, slow moves 1. If they meet → cycle. If fast hits nullptr → no cycle.

C++
bool hasCycle(ListNode* head) {
    ListNode* slow = head;
    ListNode* fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) return true;
    }
    return false;
}
// Time: O(n)  Space: O(1)

#19Remove Nth Node From EndMedium

Remove the nth node from the end of the list. One pass only.

Pattern: Move fast pointer n+1 steps ahead. Then advance both until fast is nullptr. slow is now just before the target.

C++
ListNode* removeNthFromEnd(ListNode* head, int n) {
    ListNode dummy(0, head);
    ListNode *fast = &dummy, *slow = &dummy;
    for (int i = 0; i <= n; i++) fast = fast->next;
    while (fast) { fast = fast->next; slow = slow->next; }
    slow->next = slow->next->next;
    return dummy.next;
}
// Time: O(n)  Space: O(1)

#143Reorder ListMedium

L0→L1→…→Ln → L0→Ln→L1→Ln-1→L2→Ln-2…

Pattern: (1) Find middle via fast/slow. (2) Reverse second half. (3) Interleave the two halves.

C++
void reorderList(ListNode* head) {
    // 1. Find middle
    ListNode *slow = head, *fast = head;
    while (fast->next && fast->next->next) {
        slow = slow->next; fast = fast->next->next;
    }
    // 2. Reverse second half
    ListNode *prev = nullptr, *cur = slow->next;
    slow->next = nullptr;
    while (cur) {
        ListNode* nxt = cur->next; cur->next = prev;
        prev = cur; cur = nxt;
    }
    // 3. Interleave
    ListNode *first = head, *second = prev;
    while (second) {
        ListNode *t1 = first->next, *t2 = second->next;
        first->next = second; second->next = t1;
        first = t1; second = t2;
    }
}

#2Add Two NumbersMedium

Two linked lists represent integers in reverse order. Add and return as linked list.

Pattern: Simulate digit-by-digit addition with carry. Use dummy head. Continue while any list has nodes OR carry > 0.

C++
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
    ListNode dummy(0);
    ListNode* cur = &dummy;
    int carry = 0;
    while (l1 || l2 || carry) {
        int sum = carry;
        if (l1) { sum += l1->val; l1 = l1->next; }
        if (l2) { sum += l2->val; l2 = l2->next; }
        carry = sum / 10;
        cur->next = new ListNode(sum % 10);
        cur = cur->next;
    }
    return dummy.next;
}
// Time: O(max(m,n))  Space: O(max(m,n))

#876Middle of Linked ListEasy

Return middle node. For even length, return second middle.

Pattern: Fast and slow pointers. When fast reaches end, slow is at middle.

C++
ListNode* middleNode(ListNode* head) {
    ListNode *slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}
// Time: O(n)  Space: O(1)

#25Reverse Nodes in k-GroupHard

Reverse every k nodes. If remaining < k, leave as-is.

Pattern: Check k nodes exist. Reverse k nodes. Connect to recursive result on rest.

C++
ListNode* reverseKGroup(ListNode* head, int k) {
    ListNode* cur = head;
    int count = 0;
    while (cur && count < k) { cur = cur->next; count++; }
    if (count < k) return head;   // less than k remain
    ListNode* prev = reverseKGroup(cur, k);  // recurse
    while (count--) {
        ListNode* nxt = head->next;
        head->next = prev; prev = head; head = nxt;
    }
    return prev;
}
// Time: O(n)  Space: O(n/k) call stack

#138Copy List With Random PointerMedium

Deep copy a linked list where each node has an additional random pointer that may point to any node in the list or null.

Pattern: Two-pass with a hash map: first pass creates all new nodes (old→new mapping), second pass sets next and random pointers using the map.

C++
Node* copyRandomList(Node* head) {
    if (!head) return nullptr;
    unordered_map<Node*, Node*> mp;
    Node* cur = head;
    while (cur) { mp[cur] = new Node(cur->val); cur = cur->next; }
    cur = head;
    while (cur) {
        mp[cur]->next   = mp[cur->next];    // mp[nullptr] = nullptr by default
        mp[cur]->random = mp[cur->random];
        cur = cur->next;
    }
    return mp[head];
}
// Time: O(n)  Space: O(n) — O(1) space possible with interleaving trick

Watch out: Always check cur != nullptr before accessing cur->next. The most common linked list bug: dereferencing a null pointer.