Linked Lists

Chapter 7 · Part 2: LINEAR DATA STRUCTURES · Est. 23 min read

Chapter Goal: Build complete command over linked lists — from raw node manipulation to the advanced reversal, merging, and cycle-detection patterns that appear in FAANG interviews. Linked lists demand precise pointer arithmetic. Every technique here must become second nature before your interview.

7.1 Singly Linked List — Structure, Build & Core Operations

Node Definition

// Standard LeetCode node — memorize this exactly
struct ListNode {
    int val;
    ListNode* next;
 
    ListNode()             : val(0), next(nullptr) {}
    ListNode(int x)        : val(x), next(nullptr) {}
    ListNode(int x, ListNode* next) : val(x), next(next) {}
};

Building a Linked List

// Build from a vector (useful for testing)
ListNode* buildList(vector<int> vals) {
    ListNode dummy(0);
    ListNode* tail = &dummy;
    for (int v : vals) {
        tail->next = new ListNode(v);
        tail = tail->next;
    }
    return dummy.next;
}
 
// [1] -> [2] -> [3] -> [4] -> [5] -> nullptr
ListNode* head = buildList({1, 2, 3, 4, 5});

Traversal

// Print all nodes
void printList(ListNode* head) {
    for (ListNode* curr = head; curr != nullptr; curr = curr->next) {
        cout << curr->val;
        if (curr->next) cout << " -> ";
    }
    cout << " -> nullptr\n";
}
 
// Collect values into a vector
vector<int> toVector(ListNode* head) {
    vector<int> vals;
    for (ListNode* curr = head; curr; curr = curr->next)
        vals.push_back(curr->val);
    return vals;
}
 
// Count nodes
int length(ListNode* head) {
    int len = 0;
    for (ListNode* curr = head; curr; curr = curr->next) len++;
    return len;
}

Insert Operations

// Insert at head: O(1)
ListNode* insertAtHead(ListNode* head, int val) {
    ListNode* node = new ListNode(val);
    node->next = head;
    return node;   // New head
}
 
// Insert at tail: O(n) without a tail pointer
ListNode* insertAtTail(ListNode* head, int val) {
    ListNode* node = new ListNode(val);
    if (!head) return node;
    ListNode* curr = head;
    while (curr->next) curr = curr->next;
    curr->next = node;
    return head;
}
 
// Insert after a given node: O(1) given the node
void insertAfter(ListNode* prev, int val) {
    ListNode* node = new ListNode(val);
    node->next = prev->next;
    prev->next = node;
}
 
// Insert at position k (0-indexed): O(k)
ListNode* insertAt(ListNode* head, int k, int val) {
    ListNode dummy(0, head);
    ListNode* prev = &dummy;
    for (int i = 0; i < k && prev->next; i++) prev = prev->next;
    ListNode* node = new ListNode(val);
    node->next = prev->next;
    prev->next = node;
    return dummy.next;
}

Delete Operations

// Delete head: O(1)
ListNode* deleteHead(ListNode* head) {
    if (!head) return nullptr;
    ListNode* newHead = head->next;
    delete head;
    return newHead;
}
 
// Delete first node with given value: O(n)
ListNode* deleteByValue(ListNode* head, int val) {
    ListNode dummy(0, head);
    ListNode* prev = &dummy;
 
    while (prev->next) {
        if (prev->next->val == val) {
            ListNode* toDelete = prev->next;
            prev->next = toDelete->next;   // The crucial step: bypass the node
            delete toDelete;
            break;
        }
        prev = prev->next;
    }
    return dummy.next;
}
 
// Delete ALL nodes with given value: O(n)
ListNode* deleteAllByValue(ListNode* head, int val) {
    ListNode dummy(0, head);
    ListNode* prev = &dummy;
 
    while (prev->next) {
        if (prev->next->val == val) {
            ListNode* toDelete = prev->next;
            prev->next = toDelete->next;
            delete toDelete;
            // Don't advance prev — next node may also match
        } else {
            prev = prev->next;
        }
    }
    return dummy.next;
}
 
// Critical: to delete a node you must update prev->next.
// Simply doing curr = curr->next does NOT remove the node from the list.

The Dummy Head — The Most Important Trick

A dummy head (sentinel node) placed before the true head eliminates special cases for operations that affect the head node. Use it in almost every linked list problem.

// Without dummy head: must handle head separately
ListNode* removeElements_v1(ListNode* head, int val) {
    while (head && head->val == val) head = head->next;  // Handle head
    ListNode* curr = head;
    while (curr && curr->next) {
        if (curr->next->val == val)
            curr->next = curr->next->next;
        else
            curr = curr->next;
    }
    return head;
}
 
// With dummy head: uniform handling, no special cases
ListNode* removeElements_v2(ListNode* head, int val) {
    ListNode dummy(0, head);
    ListNode* prev = &dummy;
    while (prev->next) {
        if (prev->next->val == val)
            prev->next = prev->next->next;
        else
            prev = prev->next;
    }
    return dummy.next;  // dummy.next is the (possibly new) head
}

7.2 Doubly Linked List

Node Definition

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

Insert and Delete

// Insert node after `pos`: O(1)
void insertAfter(DListNode* pos, int val) {
    DListNode* newNode = new DListNode(val);
    newNode->next = pos->next;
    newNode->prev = pos;
    if (pos->next) pos->next->prev = newNode;
    pos->next = newNode;
}
 
// Delete a node: O(1) — no need to find prev! (key advantage over singly)
void deleteNode(DListNode* node) {
    if (node->prev) node->prev->next = node->next;
    if (node->next) node->next->prev = node->prev;
    delete node;
}

When to Use Doubly Linked List

Need	Singly	Doubly
Delete given a node pointer	O(n) (must find prev)	O(1)
Traverse backwards	No	Yes
LRU / LFU Cache	Awkward	Natural fit
Browser history (forward/back)	No	Yes
Memory per node	Less (one pointer)	More (two pointers)

LRU Cache — Doubly List + Hash Map (LC 146)

class LRUCache {
    struct Node {
        int key, val;
        Node *prev, *next;
        Node(int k, int v) : key(k), val(v), prev(nullptr), next(nullptr) {}
    };
    int capacity;
    unordered_map<int, Node*> cache;
    Node* head;  // Dummy head (LRU end)
    Node* tail;  // Dummy tail (MRU end)
 
    void remove(Node* node) {
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }
    void insertAtTail(Node* node) {
        node->prev = tail->prev;
        node->next = tail;
        tail->prev->next = node;
        tail->prev = node;
    }
 
public:
    LRUCache(int cap) : capacity(cap) {
        head = new Node(0, 0);
        tail = new Node(0, 0);
        head->next = tail;
        tail->prev = head;
    }
    int get(int key) {
        if (!cache.count(key)) return -1;
        Node* node = cache[key];
        remove(node);
        insertAtTail(node);
        return node->val;
    }
    void put(int key, int value) {
        if (cache.count(key)) {
            cache[key]->val = value;
            get(key); return;
        }
        if ((int)cache.size() == capacity) {
            Node* lru = head->next;
            cache.erase(lru->key);
            remove(lru);
            delete lru;
        }
        Node* node = new Node(key, value);
        insertAtTail(node);
        cache[key] = node;
    }
};
// get: O(1), put: O(1)

7.3 Circular Linked List

In a circular singly linked list, the tail's next points back to the head.

// Building a circular list
ListNode* buildCircular(vector<int> vals) {
    if (vals.empty()) return nullptr;
    ListNode* head = new ListNode(vals[0]);
    ListNode* tail = head;
    for (int i = 1; i < (int)vals.size(); i++) {
        tail->next = new ListNode(vals[i]);
        tail = tail->next;
    }
    tail->next = head;   // Close the circle
    return head;
}
 
// Traversal uses do-while to visit head exactly once
void printCircular(ListNode* head) {
    if (!head) return;
    ListNode* curr = head;
    do {
        cout << curr->val << " ";
        curr = curr->next;
    } while (curr != head);
    cout << "\n";
}

Key fact: A circular list has no node where next == nullptr. Floyd's algorithm (Section 7.7) detects this in O(n) time, O(1) space.

7.4 Reversal Techniques — Iterative & Recursive

Reversal is the single most fundamental linked list operation. Every variation builds on the three-pointer iterative pattern.

Full Reversal — Iterative (3 Pointers)

Before:  1 -> 2 -> 3 -> 4 -> 5 -> nullptr
After:   5 -> 4 -> 3 -> 2 -> 1 -> nullptr

Step-by-step:
prev=null, curr=1:  save next=2, 1->null,  prev=1, curr=2
prev=1,    curr=2:  save next=3, 2->1,     prev=2, curr=3
prev=2,    curr=3:  save next=4, 3->2,     prev=3, curr=4
prev=3,    curr=4:  save next=5, 4->3,     prev=4, curr=5
prev=4,    curr=5:  save next=null, 5->4,  prev=5, curr=null
curr is null -> done, return prev (=5)

ListNode* reverseList(ListNode* head) {
    ListNode* prev = nullptr;
    ListNode* curr = head;
 
    while (curr) {
        ListNode* nextNode = curr->next;  // 1. Save next
        curr->next = prev;                // 2. Reverse link
        prev = curr;                      // 3. Advance prev
        curr = nextNode;                  // 4. Advance curr
    }
    return prev;   // prev is the new head
}
// Time: O(n), Space: O(1)
// Memory tip: "Save, Reverse, Advance prev, Advance curr" = SRAP

Full Reversal — Recursive

ListNode* reverseList(ListNode* head) {
    if (!head || !head->next) return head;
 
    ListNode* newHead = reverseList(head->next);
 
    // head->next is now the TAIL of the reversed sublist
    head->next->next = head;   // Point tail back to current head
    head->next = nullptr;       // Current head becomes new tail
 
    return newHead;
}
// Time: O(n), Space: O(n) — recursion stack

Partial Reversal — Reverse from Position left to right (LC 92)

ListNode* reverseBetween(ListNode* head, int left, int right) {
    ListNode dummy(0, head);
    ListNode* prev = &dummy;
 
    // Advance prev to the node BEFORE position `left`
    for (int i = 1; i < left; i++) prev = prev->next;
 
    // Reverse (right - left + 1) nodes
    ListNode* curr = prev->next, *subPrev = nullptr;
    for (int i = 0; i <= right - left; i++) {
        ListNode* next = curr->next;
        curr->next = subPrev;
        subPrev = curr;
        curr = next;
    }
    // subPrev = new head of reversed segment
    // curr    = node at position right+1
 
    prev->next->next = curr;    // Old left (now tail) -> right+1
    prev->next = subPrev;       // Node before left -> new head of reversed segment
 
    return dummy.next;
}
// Time: O(n), Space: O(1)
 
/*
  head=1->2->3->4->5, left=2, right=4
  Advance prev to node 1.
  Reverse nodes 2,3,4 -> subPrev=4->3->2, curr=5
  Reconnect: 1->next->next=5  (node 2's next = 5)
             1->next=4         (1 -> 4->3->2->5)
  Result: 1->4->3->2->5
*/

Reverse in K-Groups (LC 25)

ListNode* reverseKGroup(ListNode* head, int k) {
    // Check if at least k nodes remain
    ListNode* check = head;
    for (int i = 0; i < k; i++) {
        if (!check) return head;  // Fewer than k nodes — return unchanged
        check = check->next;
    }
 
    // Reverse exactly k nodes
    ListNode* prev = nullptr, *curr = head;
    for (int i = 0; i < k; i++) {
        ListNode* next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
 
    // head is now the tail of the reversed group
    // curr is the start of the remaining list
    head->next = reverseKGroup(curr, k);
 
    return prev;  // prev is the new head of this group
}
// Time: O(n), Space: O(n/k) — recursion depth
 
/*
  head=1->2->3->4->5, k=2
  Reverse [1,2]  -> 2->1,    recurse on [3,4,5]
    Reverse [3,4] -> 4->3,   recurse on [5]
      k=2, only 1 node -> return 5
    Connect: 3->5  ->  4->3->5
  Connect: 1->4   ->  2->1->4->3->5  ✅
*/

7.5 Fast & Slow Pointers — Middle, Nth from End, Cycle

Finding the Middle Node

// Returns second middle for even-length lists: [1,2,3,4] -> node 3
ListNode* middleNode(ListNode* head) {
    ListNode* slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}
 
// Returns FIRST middle for even-length lists: [1,2,3,4] -> node 2
// Use this when splitting for merge sort
ListNode* firstMiddle(ListNode* head) {
    ListNode* slow = head, *fast = head->next;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}
// Time: O(n), Space: O(1) for both

Removing the Nth Node From the End — Single Pass

Two-pointer with a gap of n+1 steps (using dummy head so slow stops before target).

ListNode* removeNthFromEnd(ListNode* head, int n) {
    ListNode dummy(0, head);
    ListNode* fast = &dummy;
    ListNode* slow = &dummy;
 
    // Advance fast by n+1 steps
    for (int i = 0; i <= n; i++) fast = fast->next;
 
    // Move both until fast hits null
    while (fast) {
        slow = slow->next;
        fast = fast->next;
    }
    // slow->next is the node to remove
    slow->next = slow->next->next;
 
    return dummy.next;
}
// Time: O(n), Space: O(1) — true single pass
 
/*
  head=1->2->3->4->5, n=2  (remove 4)
  dummy->1->2->3->4->5
 
  Advance fast 3 steps from dummy: fast->3
  Move both: slow=1,fast=4 | slow=2,fast=5 | slow=3,fast=null
  Remove: slow->next = 4, set slow->next = 5
  Result: 1->2->3->5  ✅
*/

7.6 Merging Sorted Lists — Two Lists & K Lists

Merge Two Sorted Lists — Iterative (O(1) Space)

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

Merge K Sorted Lists — Priority Queue

ListNode* mergeKLists(vector<ListNode*>& lists) {
    auto cmp = [](ListNode* a, ListNode* b) { return a->val > b->val; };
    priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> minPQ(cmp);
 
    for (ListNode* head : lists) if (head) minPQ.push(head);
 
    ListNode dummy(0);
    ListNode* tail = &dummy;
    while (!minPQ.empty()) {
        ListNode* node = minPQ.top(); minPQ.pop();
        tail->next = node;
        tail = tail->next;
        if (node->next) minPQ.push(node->next);
    }
    return dummy.next;
}
// Time: O(N log k) — N total nodes, k lists; each node pushed/popped once
// Space: O(k) — heap holds at most k nodes

Merge K Sorted Lists — Divide & Conquer

ListNode* mergeKLists(vector<ListNode*>& lists) {
    if (lists.empty()) return nullptr;
    return mergeRange(lists, 0, lists.size() - 1);
}
ListNode* mergeRange(vector<ListNode*>& lists, int lo, int hi) {
    if (lo == hi) return lists[lo];
    int mid = lo + (hi - lo) / 2;
    return mergeTwoLists(mergeRange(lists, lo, mid),
                         mergeRange(lists, mid+1, hi));
}
// Time: O(N log k), Space: O(log k) recursion depth

7.7 Detecting & Removing Cycles — Floyd's Complete Treatment

Phase 1 — Detect Cycle

bool hasCycle(ListNode* head) {
    ListNode* slow = head, *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)

Phase 2 — Find Cycle Entry Point

Mathematical Proof:
  F = distance from head to cycle entry
  C = cycle length
  k = distance from entry to meeting point

  At meeting: slow traveled F+k, fast traveled F+k+m*C (lapped m times)
  Since fast = 2*slow:
    F + k + m*C = 2(F + k)
    F = m*C - k

  Key: from the meeting point, going F more steps reaches the entry.
  Simultaneously, head is also F steps from the entry.
  Both pointers meet at the cycle entry.

ListNode* detectCycle(ListNode* head) {
    ListNode* slow = head, *fast = head;
 
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) {
            // Phase 2: reset slow to head, keep fast at meeting point
            slow = head;
            while (slow != fast) {
                slow = slow->next;
                fast = fast->next;  // Both move ONE step now
            }
            return slow;  // Cycle entry
        }
    }
    return nullptr;
}
// Time: O(n), Space: O(1)

Remove the Cycle

void removeCycle(ListNode* head) {
    ListNode* entry = detectCycle(head);
    if (!entry) return;
    // Walk from entry until we find the last node of the cycle
    ListNode* prev = entry;
    while (prev->next != entry) prev = prev->next;
    prev->next = nullptr;  // Break the cycle
}

7.8 Essential Linked List Patterns & Tricks

Pattern 1 — Palindrome Check via Reversal

1. Find middle (fast/slow)
2. Reverse second half in place
3. Compare first and reversed second half
4. (Restore if needed)

bool isPalindrome(ListNode* head) {
    if (!head || !head->next) return true;
    ListNode* slow = head, *fast = head;
    while (fast && fast->next) { slow = slow->next; fast = fast->next->next; }
 
    // Reverse second half starting at slow
    ListNode* prev = nullptr, *curr = slow;
    while (curr) { ListNode* next=curr->next; curr->next=prev; prev=curr; curr=next; }
 
    ListNode* l = head, *r = prev;
    while (r) {
        if (l->val != r->val) return false;
        l = l->next; r = r->next;
    }
    return true;
}
// Time: O(n), Space: O(1)

Pattern 2 — Intersection of Two Lists (LC 160)

// Redirect each pointer to the other list's head when it reaches null.
// Both travel m+n steps total and meet at intersection (or null).
ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
    ListNode* a = headA, *b = headB;
    while (a != b) {
        a = a ? a->next : headB;
        b = b ? b->next : headA;
    }
    return a;  // null if no intersection
}
// Time: O(m + n), Space: O(1)

Pattern 3 — Copy List with Random Pointer (LC 138)

// Approach: HashMap original -> copy node
Node* copyRandomList(Node* head) {
    if (!head) return nullptr;
    unordered_map<Node*, Node*> mp;
    for (Node* c = head; c; c = c->next) mp[c] = new Node(c->val);
    for (Node* c = head; c; c = c->next) {
        if (c->next)   mp[c]->next   = mp[c->next];
        if (c->random) mp[c]->random = mp[c->random];
    }
    return mp[head];
}
// Time: O(n), Space: O(n)

Pattern 4 — In-Place Rearrangement (Odd-Even, LC 328)

ListNode* oddEvenList(ListNode* head) {
    if (!head) return head;
    ListNode* odd = head, *even = head->next, *evenHead = even;
    while (even && even->next) {
        odd->next  = even->next;  // Connect odd to next odd node
        odd        = odd->next;
        even->next = odd->next;   // Connect even to next even node
        even       = even->next;
    }
    odd->next = evenHead;   // Attach even chain to end of odd chain
    return head;
}
// Time: O(n), Space: O(1)

7.9 Sample Problems

Problem 1 — Reverse Linked List (Easy) — LC 206

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

Problem 2 — Merge Two Sorted Lists (Easy) — LC 21

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

Problem 3 — Palindrome Linked List (Easy) — LC 234

bool isPalindrome(ListNode* head) {
    ListNode* slow = head, *fast = head;
    while (fast && fast->next) { slow = slow->next; fast = fast->next->next; }
    ListNode* prev = nullptr, *curr = slow;
    while (curr) { ListNode* next=curr->next; curr->next=prev; prev=curr; curr=next; }
    ListNode* l = head, *r = prev;
    while (r) { if (l->val != r->val) return false; l=l->next; r=r->next; }
    return true;
}
// Time: O(n), Space: O(1)

Problem 4 — Remove Nth Node From End (Medium) — LC 19

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) { slow = slow->next; fast = fast->next; }
    slow->next = slow->next->next;
    return dummy.next;
}
// Time: O(n), Space: O(1)

Problem 5 — Add Two Numbers (Medium) — LC 2

ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
    ListNode dummy(0);
    ListNode* curr = &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;
        curr->next = new ListNode(sum % 10);
        curr = curr->next;
    }
    return dummy.next;
}
// Time: O(max(n,m)), Space: O(max(n,m))

Problem 6 — Odd Even Linked List (Medium) — LC 328

ListNode* oddEvenList(ListNode* head) {
    if (!head) return head;
    ListNode* odd = head, *even = head->next, *evenHead = even;
    while (even && even->next) {
        odd->next = even->next; odd = odd->next;
        even->next = odd->next; even = even->next;
    }
    odd->next = evenHead;
    return head;
}
// Time: O(n), Space: O(1)

Problem 7 — Linked List Cycle II (Medium) — LC 142

ListNode* detectCycle(ListNode* head) {
    ListNode* slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next; fast = fast->next->next;
        if (slow == fast) {
            slow = head;
            while (slow != fast) { slow = slow->next; fast = fast->next; }
            return slow;
        }
    }
    return nullptr;
}
// Time: O(n), Space: O(1)

Problem 8 — Reverse Linked List II (Medium) — LC 92

ListNode* reverseBetween(ListNode* head, int left, int right) {
    ListNode dummy(0, head);
    ListNode* prev = &dummy;
    for (int i = 1; i < left; i++) prev = prev->next;
    ListNode* curr = prev->next, *subPrev = nullptr;
    for (int i = 0; i <= right - left; i++) {
        ListNode* next = curr->next; curr->next = subPrev; subPrev = curr; curr = next;
    }
    prev->next->next = curr;
    prev->next = subPrev;
    return dummy.next;
}
// Time: O(n), Space: O(1)

Problem 9 — Copy List with Random Pointer (Medium) — LC 138

Node* copyRandomList(Node* head) {
    if (!head) return nullptr;
    unordered_map<Node*, Node*> mp;
    for (Node* c = head; c; c = c->next) mp[c] = new Node(c->val);
    for (Node* c = head; c; c = c->next) {
        if (c->next)   mp[c]->next   = mp[c->next];
        if (c->random) mp[c]->random = mp[c->random];
    }
    return mp[head];
}
// Time: O(n), Space: O(n)

Problem 10 — Sort List (Medium) — LC 148

ListNode* sortList(ListNode* head) {
    if (!head || !head->next) return head;
    // Find first middle (start fast at head->next for clean split)
    ListNode* slow = head, *fast = head->next;
    while (fast && fast->next) { slow = slow->next; fast = fast->next->next; }
    ListNode* mid = slow->next;
    slow->next = nullptr;  // Split list in half
    return mergeTwoLists(sortList(head), sortList(mid));
}
// Time: O(n log n), Space: O(log n) — recursion stack

Problem 11 — Merge k Sorted Lists (Hard) — LC 23

ListNode* mergeKLists(vector<ListNode*>& lists) {
    auto cmp = [](ListNode* a, ListNode* b) { return a->val > b->val; };
    priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> pq(cmp);
    for (ListNode* h : lists) if (h) pq.push(h);
    ListNode dummy(0); ListNode* tail = &dummy;
    while (!pq.empty()) {
        ListNode* node = pq.top(); pq.pop();
        tail->next = node; tail = tail->next;
        if (node->next) pq.push(node->next);
    }
    return dummy.next;
}
// Time: O(N log k), Space: O(k)

Problem 12 — Reverse Nodes in k-Group (Hard) — LC 25

ListNode* reverseKGroup(ListNode* head, int k) {
    ListNode* node = head;
    for (int i = 0; i < k; i++) {
        if (!node) return head;  // Fewer than k nodes — don't reverse
        node = node->next;
    }
    ListNode* prev = nullptr, *curr = head;
    for (int i = 0; i < k; i++) {
        ListNode* next = curr->next; curr->next = prev; prev = curr; curr = next;
    }
    head->next = reverseKGroup(curr, k);
    return prev;
}
// Time: O(n), Space: O(n/k)

7.10 LeetCode Problem Set

#	Problem	Difficulty	Core Technique	Link
1	Reverse Linked List	Easy	3-pointer iterative (SRAP)	LC 206
2	Merge Two Sorted Lists	Easy	Dummy head + compare	LC 21
3	Remove Nth Node From End	Medium	Two-pointer gap (n+1)	LC 19
4	Add Two Numbers	Medium	Carry propagation, dummy head	LC 2
5	Linked List Cycle II	Medium	Floyd's Phase 1 + Phase 2	LC 142
6	Copy List with Random Pointer	Medium	Hash map clone	LC 138
7	Merge k Sorted Lists	Hard	Min-heap / Divide & Conquer	LC 23
8	Reverse Nodes in k-Group	Hard	k-group reversal + recursion	LC 25

Suggested order: Master #1 and #2 (building blocks). Then #3 and #5 (pointer patterns). Then #4 and #6 (medium depth). #7 and #8 are the hard benchmarks — both require bug-free pointer manipulation under pressure.

Linked Lists

Chapter 7 · Part 2: LINEAR DATA STRUCTURES · Est. 23 min read

Chapter Goal: Build complete command over linked lists — from raw node manipulation to the advanced reversal, merging, and cycle-detection patterns that appear in FAANG interviews. Linked lists demand precise pointer arithmetic. Every technique here must become second nature before your interview.

7.1 Singly Linked List — Structure, Build & Core Operations

Node Definition

// Standard LeetCode node — memorize this exactly
struct ListNode {
    int val;
    ListNode* next;
 
    ListNode()             : val(0), next(nullptr) {}
    ListNode(int x)        : val(x), next(nullptr) {}
    ListNode(int x, ListNode* next) : val(x), next(next) {}
};

Building a Linked List

// Build from a vector (useful for testing)
ListNode* buildList(vector<int> vals) {
    ListNode dummy(0);
    ListNode* tail = &dummy;
    for (int v : vals) {
        tail->next = new ListNode(v);
        tail = tail->next;
    }
    return dummy.next;
}
 
// [1] -> [2] -> [3] -> [4] -> [5] -> nullptr
ListNode* head = buildList({1, 2, 3, 4, 5});

Traversal

// Print all nodes
void printList(ListNode* head) {
    for (ListNode* curr = head; curr != nullptr; curr = curr->next) {
        cout << curr->val;
        if (curr->next) cout << " -> ";
    }
    cout << " -> nullptr\n";
}
 
// Collect values into a vector
vector<int> toVector(ListNode* head) {
    vector<int> vals;
    for (ListNode* curr = head; curr; curr = curr->next)
        vals.push_back(curr->val);
    return vals;
}
 
// Count nodes
int length(ListNode* head) {
    int len = 0;
    for (ListNode* curr = head; curr; curr = curr->next) len++;
    return len;
}

Insert Operations

// Insert at head: O(1)
ListNode* insertAtHead(ListNode* head, int val) {
    ListNode* node = new ListNode(val);
    node->next = head;
    return node;   // New head
}
 
// Insert at tail: O(n) without a tail pointer
ListNode* insertAtTail(ListNode* head, int val) {
    ListNode* node = new ListNode(val);
    if (!head) return node;
    ListNode* curr = head;
    while (curr->next) curr = curr->next;
    curr->next = node;
    return head;
}
 
// Insert after a given node: O(1) given the node
void insertAfter(ListNode* prev, int val) {
    ListNode* node = new ListNode(val);
    node->next = prev->next;
    prev->next = node;
}
 
// Insert at position k (0-indexed): O(k)
ListNode* insertAt(ListNode* head, int k, int val) {
    ListNode dummy(0, head);
    ListNode* prev = &dummy;
    for (int i = 0; i < k && prev->next; i++) prev = prev->next;
    ListNode* node = new ListNode(val);
    node->next = prev->next;
    prev->next = node;
    return dummy.next;
}

Delete Operations

// Delete head: O(1)
ListNode* deleteHead(ListNode* head) {
    if (!head) return nullptr;
    ListNode* newHead = head->next;
    delete head;
    return newHead;
}
 
// Delete first node with given value: O(n)
ListNode* deleteByValue(ListNode* head, int val) {
    ListNode dummy(0, head);
    ListNode* prev = &dummy;
 
    while (prev->next) {
        if (prev->next->val == val) {
            ListNode* toDelete = prev->next;
            prev->next = toDelete->next;   // The crucial step: bypass the node
            delete toDelete;
            break;
        }
        prev = prev->next;
    }
    return dummy.next;
}
 
// Delete ALL nodes with given value: O(n)
ListNode* deleteAllByValue(ListNode* head, int val) {
    ListNode dummy(0, head);
    ListNode* prev = &dummy;
 
    while (prev->next) {
        if (prev->next->val == val) {
            ListNode* toDelete = prev->next;
            prev->next = toDelete->next;
            delete toDelete;
            // Don't advance prev — next node may also match
        } else {
            prev = prev->next;
        }
    }
    return dummy.next;
}
 
// Critical: to delete a node you must update prev->next.
// Simply doing curr = curr->next does NOT remove the node from the list.

The Dummy Head — The Most Important Trick

A dummy head (sentinel node) placed before the true head eliminates special cases for operations that affect the head node. Use it in almost every linked list problem.

// Without dummy head: must handle head separately
ListNode* removeElements_v1(ListNode* head, int val) {
    while (head && head->val == val) head = head->next;  // Handle head
    ListNode* curr = head;
    while (curr && curr->next) {
        if (curr->next->val == val)
            curr->next = curr->next->next;
        else
            curr = curr->next;
    }
    return head;
}
 
// With dummy head: uniform handling, no special cases
ListNode* removeElements_v2(ListNode* head, int val) {
    ListNode dummy(0, head);
    ListNode* prev = &dummy;
    while (prev->next) {
        if (prev->next->val == val)
            prev->next = prev->next->next;
        else
            prev = prev->next;
    }
    return dummy.next;  // dummy.next is the (possibly new) head
}

7.2 Doubly Linked List

Node Definition

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

Insert and Delete

// Insert node after `pos`: O(1)
void insertAfter(DListNode* pos, int val) {
    DListNode* newNode = new DListNode(val);
    newNode->next = pos->next;
    newNode->prev = pos;
    if (pos->next) pos->next->prev = newNode;
    pos->next = newNode;
}
 
// Delete a node: O(1) — no need to find prev! (key advantage over singly)
void deleteNode(DListNode* node) {
    if (node->prev) node->prev->next = node->next;
    if (node->next) node->next->prev = node->prev;
    delete node;
}

When to Use Doubly Linked List

Need	Singly	Doubly
Delete given a node pointer	O(n) (must find prev)	O(1)
Traverse backwards	No	Yes
LRU / LFU Cache	Awkward	Natural fit
Browser history (forward/back)	No	Yes
Memory per node	Less (one pointer)	More (two pointers)

LRU Cache — Doubly List + Hash Map (LC 146)

class LRUCache {
    struct Node {
        int key, val;
        Node *prev, *next;
        Node(int k, int v) : key(k), val(v), prev(nullptr), next(nullptr) {}
    };
    int capacity;
    unordered_map<int, Node*> cache;
    Node* head;  // Dummy head (LRU end)
    Node* tail;  // Dummy tail (MRU end)
 
    void remove(Node* node) {
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }
    void insertAtTail(Node* node) {
        node->prev = tail->prev;
        node->next = tail;
        tail->prev->next = node;
        tail->prev = node;
    }
 
public:
    LRUCache(int cap) : capacity(cap) {
        head = new Node(0, 0);
        tail = new Node(0, 0);
        head->next = tail;
        tail->prev = head;
    }
    int get(int key) {
        if (!cache.count(key)) return -1;
        Node* node = cache[key];
        remove(node);
        insertAtTail(node);
        return node->val;
    }
    void put(int key, int value) {
        if (cache.count(key)) {
            cache[key]->val = value;
            get(key); return;
        }
        if ((int)cache.size() == capacity) {
            Node* lru = head->next;
            cache.erase(lru->key);
            remove(lru);
            delete lru;
        }
        Node* node = new Node(key, value);
        insertAtTail(node);
        cache[key] = node;
    }
};
// get: O(1), put: O(1)

7.3 Circular Linked List

In a circular singly linked list, the tail's next points back to the head.

// Building a circular list
ListNode* buildCircular(vector<int> vals) {
    if (vals.empty()) return nullptr;
    ListNode* head = new ListNode(vals[0]);
    ListNode* tail = head;
    for (int i = 1; i < (int)vals.size(); i++) {
        tail->next = new ListNode(vals[i]);
        tail = tail->next;
    }
    tail->next = head;   // Close the circle
    return head;
}
 
// Traversal uses do-while to visit head exactly once
void printCircular(ListNode* head) {
    if (!head) return;
    ListNode* curr = head;
    do {
        cout << curr->val << " ";
        curr = curr->next;
    } while (curr != head);
    cout << "\n";
}

Key fact: A circular list has no node where next == nullptr. Floyd's algorithm (Section 7.7) detects this in O(n) time, O(1) space.

7.4 Reversal Techniques — Iterative & Recursive

Reversal is the single most fundamental linked list operation. Every variation builds on the three-pointer iterative pattern.

Full Reversal — Iterative (3 Pointers)

Before:  1 -> 2 -> 3 -> 4 -> 5 -> nullptr
After:   5 -> 4 -> 3 -> 2 -> 1 -> nullptr

Step-by-step:
prev=null, curr=1:  save next=2, 1->null,  prev=1, curr=2
prev=1,    curr=2:  save next=3, 2->1,     prev=2, curr=3
prev=2,    curr=3:  save next=4, 3->2,     prev=3, curr=4
prev=3,    curr=4:  save next=5, 4->3,     prev=4, curr=5
prev=4,    curr=5:  save next=null, 5->4,  prev=5, curr=null
curr is null -> done, return prev (=5)

ListNode* reverseList(ListNode* head) {
    ListNode* prev = nullptr;
    ListNode* curr = head;
 
    while (curr) {
        ListNode* nextNode = curr->next;  // 1. Save next
        curr->next = prev;                // 2. Reverse link
        prev = curr;                      // 3. Advance prev
        curr = nextNode;                  // 4. Advance curr
    }
    return prev;   // prev is the new head
}
// Time: O(n), Space: O(1)
// Memory tip: "Save, Reverse, Advance prev, Advance curr" = SRAP

Full Reversal — Recursive

ListNode* reverseList(ListNode* head) {
    if (!head || !head->next) return head;
 
    ListNode* newHead = reverseList(head->next);
 
    // head->next is now the TAIL of the reversed sublist
    head->next->next = head;   // Point tail back to current head
    head->next = nullptr;       // Current head becomes new tail
 
    return newHead;
}
// Time: O(n), Space: O(n) — recursion stack

Partial Reversal — Reverse from Position left to right (LC 92)

ListNode* reverseBetween(ListNode* head, int left, int right) {
    ListNode dummy(0, head);
    ListNode* prev = &dummy;
 
    // Advance prev to the node BEFORE position `left`
    for (int i = 1; i < left; i++) prev = prev->next;
 
    // Reverse (right - left + 1) nodes
    ListNode* curr = prev->next, *subPrev = nullptr;
    for (int i = 0; i <= right - left; i++) {
        ListNode* next = curr->next;
        curr->next = subPrev;
        subPrev = curr;
        curr = next;
    }
    // subPrev = new head of reversed segment
    // curr    = node at position right+1
 
    prev->next->next = curr;    // Old left (now tail) -> right+1
    prev->next = subPrev;       // Node before left -> new head of reversed segment
 
    return dummy.next;
}
// Time: O(n), Space: O(1)
 
/*
  head=1->2->3->4->5, left=2, right=4
  Advance prev to node 1.
  Reverse nodes 2,3,4 -> subPrev=4->3->2, curr=5
  Reconnect: 1->next->next=5  (node 2's next = 5)
             1->next=4         (1 -> 4->3->2->5)
  Result: 1->4->3->2->5
*/

Reverse in K-Groups (LC 25)

ListNode* reverseKGroup(ListNode* head, int k) {
    // Check if at least k nodes remain
    ListNode* check = head;
    for (int i = 0; i < k; i++) {
        if (!check) return head;  // Fewer than k nodes — return unchanged
        check = check->next;
    }
 
    // Reverse exactly k nodes
    ListNode* prev = nullptr, *curr = head;
    for (int i = 0; i < k; i++) {
        ListNode* next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
 
    // head is now the tail of the reversed group
    // curr is the start of the remaining list
    head->next = reverseKGroup(curr, k);
 
    return prev;  // prev is the new head of this group
}
// Time: O(n), Space: O(n/k) — recursion depth
 
/*
  head=1->2->3->4->5, k=2
  Reverse [1,2]  -> 2->1,    recurse on [3,4,5]
    Reverse [3,4] -> 4->3,   recurse on [5]
      k=2, only 1 node -> return 5
    Connect: 3->5  ->  4->3->5
  Connect: 1->4   ->  2->1->4->3->5  ✅
*/

7.5 Fast & Slow Pointers — Middle, Nth from End, Cycle

Finding the Middle Node

// Returns second middle for even-length lists: [1,2,3,4] -> node 3
ListNode* middleNode(ListNode* head) {
    ListNode* slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}
 
// Returns FIRST middle for even-length lists: [1,2,3,4] -> node 2
// Use this when splitting for merge sort
ListNode* firstMiddle(ListNode* head) {
    ListNode* slow = head, *fast = head->next;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}
// Time: O(n), Space: O(1) for both

Removing the Nth Node From the End — Single Pass

Two-pointer with a gap of n+1 steps (using dummy head so slow stops before target).

ListNode* removeNthFromEnd(ListNode* head, int n) {
    ListNode dummy(0, head);
    ListNode* fast = &dummy;
    ListNode* slow = &dummy;
 
    // Advance fast by n+1 steps
    for (int i = 0; i <= n; i++) fast = fast->next;
 
    // Move both until fast hits null
    while (fast) {
        slow = slow->next;
        fast = fast->next;
    }
    // slow->next is the node to remove
    slow->next = slow->next->next;
 
    return dummy.next;
}
// Time: O(n), Space: O(1) — true single pass
 
/*
  head=1->2->3->4->5, n=2  (remove 4)
  dummy->1->2->3->4->5
 
  Advance fast 3 steps from dummy: fast->3
  Move both: slow=1,fast=4 | slow=2,fast=5 | slow=3,fast=null
  Remove: slow->next = 4, set slow->next = 5
  Result: 1->2->3->5  ✅
*/

7.6 Merging Sorted Lists — Two Lists & K Lists

Merge Two Sorted Lists — Iterative (O(1) Space)

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

Merge K Sorted Lists — Priority Queue

ListNode* mergeKLists(vector<ListNode*>& lists) {
    auto cmp = [](ListNode* a, ListNode* b) { return a->val > b->val; };
    priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> minPQ(cmp);
 
    for (ListNode* head : lists) if (head) minPQ.push(head);
 
    ListNode dummy(0);
    ListNode* tail = &dummy;
    while (!minPQ.empty()) {
        ListNode* node = minPQ.top(); minPQ.pop();
        tail->next = node;
        tail = tail->next;
        if (node->next) minPQ.push(node->next);
    }
    return dummy.next;
}
// Time: O(N log k) — N total nodes, k lists; each node pushed/popped once
// Space: O(k) — heap holds at most k nodes

Merge K Sorted Lists — Divide & Conquer

ListNode* mergeKLists(vector<ListNode*>& lists) {
    if (lists.empty()) return nullptr;
    return mergeRange(lists, 0, lists.size() - 1);
}
ListNode* mergeRange(vector<ListNode*>& lists, int lo, int hi) {
    if (lo == hi) return lists[lo];
    int mid = lo + (hi - lo) / 2;
    return mergeTwoLists(mergeRange(lists, lo, mid),
                         mergeRange(lists, mid+1, hi));
}
// Time: O(N log k), Space: O(log k) recursion depth

7.7 Detecting & Removing Cycles — Floyd's Complete Treatment

Phase 1 — Detect Cycle

bool hasCycle(ListNode* head) {
    ListNode* slow = head, *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)

Phase 2 — Find Cycle Entry Point

Mathematical Proof:
  F = distance from head to cycle entry
  C = cycle length
  k = distance from entry to meeting point

  At meeting: slow traveled F+k, fast traveled F+k+m*C (lapped m times)
  Since fast = 2*slow:
    F + k + m*C = 2(F + k)
    F = m*C - k

  Key: from the meeting point, going F more steps reaches the entry.
  Simultaneously, head is also F steps from the entry.
  Both pointers meet at the cycle entry.

ListNode* detectCycle(ListNode* head) {
    ListNode* slow = head, *fast = head;
 
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) {
            // Phase 2: reset slow to head, keep fast at meeting point
            slow = head;
            while (slow != fast) {
                slow = slow->next;
                fast = fast->next;  // Both move ONE step now
            }
            return slow;  // Cycle entry
        }
    }
    return nullptr;
}
// Time: O(n), Space: O(1)

Remove the Cycle

void removeCycle(ListNode* head) {
    ListNode* entry = detectCycle(head);
    if (!entry) return;
    // Walk from entry until we find the last node of the cycle
    ListNode* prev = entry;
    while (prev->next != entry) prev = prev->next;
    prev->next = nullptr;  // Break the cycle
}

7.8 Essential Linked List Patterns & Tricks

Pattern 1 — Palindrome Check via Reversal

1. Find middle (fast/slow)
2. Reverse second half in place
3. Compare first and reversed second half
4. (Restore if needed)

bool isPalindrome(ListNode* head) {
    if (!head || !head->next) return true;
    ListNode* slow = head, *fast = head;
    while (fast && fast->next) { slow = slow->next; fast = fast->next->next; }
 
    // Reverse second half starting at slow
    ListNode* prev = nullptr, *curr = slow;
    while (curr) { ListNode* next=curr->next; curr->next=prev; prev=curr; curr=next; }
 
    ListNode* l = head, *r = prev;
    while (r) {
        if (l->val != r->val) return false;
        l = l->next; r = r->next;
    }
    return true;
}
// Time: O(n), Space: O(1)

Pattern 2 — Intersection of Two Lists (LC 160)

// Redirect each pointer to the other list's head when it reaches null.
// Both travel m+n steps total and meet at intersection (or null).
ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
    ListNode* a = headA, *b = headB;
    while (a != b) {
        a = a ? a->next : headB;
        b = b ? b->next : headA;
    }
    return a;  // null if no intersection
}
// Time: O(m + n), Space: O(1)

Pattern 3 — Copy List with Random Pointer (LC 138)

// Approach: HashMap original -> copy node
Node* copyRandomList(Node* head) {
    if (!head) return nullptr;
    unordered_map<Node*, Node*> mp;
    for (Node* c = head; c; c = c->next) mp[c] = new Node(c->val);
    for (Node* c = head; c; c = c->next) {
        if (c->next)   mp[c]->next   = mp[c->next];
        if (c->random) mp[c]->random = mp[c->random];
    }
    return mp[head];
}
// Time: O(n), Space: O(n)

Pattern 4 — In-Place Rearrangement (Odd-Even, LC 328)

ListNode* oddEvenList(ListNode* head) {
    if (!head) return head;
    ListNode* odd = head, *even = head->next, *evenHead = even;
    while (even && even->next) {
        odd->next  = even->next;  // Connect odd to next odd node
        odd        = odd->next;
        even->next = odd->next;   // Connect even to next even node
        even       = even->next;
    }
    odd->next = evenHead;   // Attach even chain to end of odd chain
    return head;
}
// Time: O(n), Space: O(1)

7.9 Sample Problems

Problem 1 — Reverse Linked List (Easy) — LC 206

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

Problem 2 — Merge Two Sorted Lists (Easy) — LC 21

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

Problem 3 — Palindrome Linked List (Easy) — LC 234

bool isPalindrome(ListNode* head) {
    ListNode* slow = head, *fast = head;
    while (fast && fast->next) { slow = slow->next; fast = fast->next->next; }
    ListNode* prev = nullptr, *curr = slow;
    while (curr) { ListNode* next=curr->next; curr->next=prev; prev=curr; curr=next; }
    ListNode* l = head, *r = prev;
    while (r) { if (l->val != r->val) return false; l=l->next; r=r->next; }
    return true;
}
// Time: O(n), Space: O(1)

Problem 4 — Remove Nth Node From End (Medium) — LC 19

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) { slow = slow->next; fast = fast->next; }
    slow->next = slow->next->next;
    return dummy.next;
}
// Time: O(n), Space: O(1)

Problem 5 — Add Two Numbers (Medium) — LC 2

ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
    ListNode dummy(0);
    ListNode* curr = &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;
        curr->next = new ListNode(sum % 10);
        curr = curr->next;
    }
    return dummy.next;
}
// Time: O(max(n,m)), Space: O(max(n,m))

Problem 6 — Odd Even Linked List (Medium) — LC 328

ListNode* oddEvenList(ListNode* head) {
    if (!head) return head;
    ListNode* odd = head, *even = head->next, *evenHead = even;
    while (even && even->next) {
        odd->next = even->next; odd = odd->next;
        even->next = odd->next; even = even->next;
    }
    odd->next = evenHead;
    return head;
}
// Time: O(n), Space: O(1)

Problem 7 — Linked List Cycle II (Medium) — LC 142

ListNode* detectCycle(ListNode* head) {
    ListNode* slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next; fast = fast->next->next;
        if (slow == fast) {
            slow = head;
            while (slow != fast) { slow = slow->next; fast = fast->next; }
            return slow;
        }
    }
    return nullptr;
}
// Time: O(n), Space: O(1)

Problem 8 — Reverse Linked List II (Medium) — LC 92

ListNode* reverseBetween(ListNode* head, int left, int right) {
    ListNode dummy(0, head);
    ListNode* prev = &dummy;
    for (int i = 1; i < left; i++) prev = prev->next;
    ListNode* curr = prev->next, *subPrev = nullptr;
    for (int i = 0; i <= right - left; i++) {
        ListNode* next = curr->next; curr->next = subPrev; subPrev = curr; curr = next;
    }
    prev->next->next = curr;
    prev->next = subPrev;
    return dummy.next;
}
// Time: O(n), Space: O(1)

Problem 9 — Copy List with Random Pointer (Medium) — LC 138

Node* copyRandomList(Node* head) {
    if (!head) return nullptr;
    unordered_map<Node*, Node*> mp;
    for (Node* c = head; c; c = c->next) mp[c] = new Node(c->val);
    for (Node* c = head; c; c = c->next) {
        if (c->next)   mp[c]->next   = mp[c->next];
        if (c->random) mp[c]->random = mp[c->random];
    }
    return mp[head];
}
// Time: O(n), Space: O(n)

Problem 10 — Sort List (Medium) — LC 148

ListNode* sortList(ListNode* head) {
    if (!head || !head->next) return head;
    // Find first middle (start fast at head->next for clean split)
    ListNode* slow = head, *fast = head->next;
    while (fast && fast->next) { slow = slow->next; fast = fast->next->next; }
    ListNode* mid = slow->next;
    slow->next = nullptr;  // Split list in half
    return mergeTwoLists(sortList(head), sortList(mid));
}
// Time: O(n log n), Space: O(log n) — recursion stack

Problem 11 — Merge k Sorted Lists (Hard) — LC 23

ListNode* mergeKLists(vector<ListNode*>& lists) {
    auto cmp = [](ListNode* a, ListNode* b) { return a->val > b->val; };
    priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> pq(cmp);
    for (ListNode* h : lists) if (h) pq.push(h);
    ListNode dummy(0); ListNode* tail = &dummy;
    while (!pq.empty()) {
        ListNode* node = pq.top(); pq.pop();
        tail->next = node; tail = tail->next;
        if (node->next) pq.push(node->next);
    }
    return dummy.next;
}
// Time: O(N log k), Space: O(k)

Problem 12 — Reverse Nodes in k-Group (Hard) — LC 25

ListNode* reverseKGroup(ListNode* head, int k) {
    ListNode* node = head;
    for (int i = 0; i < k; i++) {
        if (!node) return head;  // Fewer than k nodes — don't reverse
        node = node->next;
    }
    ListNode* prev = nullptr, *curr = head;
    for (int i = 0; i < k; i++) {
        ListNode* next = curr->next; curr->next = prev; prev = curr; curr = next;
    }
    head->next = reverseKGroup(curr, k);
    return prev;
}
// Time: O(n), Space: O(n/k)

7.10 LeetCode Problem Set

#	Problem	Difficulty	Core Technique	Link
1	Reverse Linked List	Easy	3-pointer iterative (SRAP)	LC 206
2	Merge Two Sorted Lists	Easy	Dummy head + compare	LC 21
3	Remove Nth Node From End	Medium	Two-pointer gap (n+1)	LC 19
4	Add Two Numbers	Medium	Carry propagation, dummy head	LC 2
5	Linked List Cycle II	Medium	Floyd's Phase 1 + Phase 2	LC 142
6	Copy List with Random Pointer	Medium	Hash map clone	LC 138
7	Merge k Sorted Lists	Hard	Min-heap / Divide & Conquer	LC 23
8	Reverse Nodes in k-Group	Hard	k-group reversal + recursion	LC 25

Suggested order: Master #1 and #2 (building blocks). Then #3 and #5 (pointer patterns). Then #4 and #6 (medium depth). #7 and #8 are the hard benchmarks — both require bug-free pointer manipulation under pressure.