Module 03: Linked Lists — Pointer Mechanics, Reversals & Cycles

Goal: Master pointer manipulation, linked list architecture (Singly, Doubly, Circular), memory ownership, Floyd's Cycle Detection mathematical proofs, in-place reversals, and composite data structure designs (LRU Cache).
Language: C++ (C++17/C++20)
Prerequisites: Module 01 (Complexity) & Module 02 (Arrays/Strings).

📑 Table of Contents

Under the Hood: Node Architecture & Memory Layout
C++ Implementation from Scratch (Singly & Doubly)
The Sentinel (Dummy Node) Pattern
Pattern 1: Fast & Slow Pointers (Floyd's Cycle Detection)
Pattern 2: In-Place Reversal Mechanics (Iterative & Recursive)
Pattern 3: Merging & Interleaving Lists
5 Practice Problems with Detailed Solutions
Top 10 FAANG Interview Questions

1. Under the Hood: Node Architecture & Memory Layout

Unlike arrays, linked lists allocate memory on the heap node-by-node. Each node contains data and one or more pointers to other nodes.

Singly Linked List Node (64-bit OS):
┌───────────────┬──────────────────────┐
│  val (4 bytes)│ next ptr (8 bytes)   │  Total: 12 bytes + 4 bytes padding = 16 bytes
└───────────────┴──────────────────────┘

Heap Layout (Non-Contiguous):
Address:   0x2040                  0x1080                  0x5020
Node:     [ 10 | 0x1080 ]  ───►  [ 20 | 0x5020 ]  ───►  [ 30 | nullptr ]

1.1 Array vs Linked List Tradeoffs

Feature	`std::vector` (Array)	`std::list` (Doubly Linked List)
Random Access ($A[i]$)	$O(1)$	$O(N)$ (requires traversal)
Insert / Delete at Head	$O(N)$ (shifts elements)	$O(1)$
Insert / Delete at Tail	Amortized $O(1)$	$O(1)$ (with tail pointer)
Insert / Delete given Node Pointer	$O(N)$ (shifting)	$O(1)$ (pointer rewiring)
Memory Overhead	Minimal (contiguous)	High (8–16 bytes pointer overhead per node)
CPU Cache Friendliness	Extremely High (Cache lines pre-fetched)	Poor (Pointer chasing causes Cache Misses)

2. C++ Implementation from Scratch (Singly & Doubly)

2.1 Singly Linked List Node

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) {}
};

2.2 Doubly Linked List Node

struct DoubleListNode {
    int key;
    int val;
    DoubleListNode* prev;
    DoubleListNode* next;
    DoubleListNode(int k, int v) : key(k), val(v), prev(nullptr), next(nullptr) {}
};

3. The Sentinel (Dummy Node) Pattern

A Sentinel (Dummy) Node is a temporary placeholder placed before the head of a list. It eliminates special-case branching for operations modifying the head (inserting before head, deleting head, merging).

Without Dummy Node:
if (head == nullptr) { ... }
if (node == head) { head = head->next; delete node; }

With Dummy Node:
ListNode dummy(0);
dummy.next = head;
ListNode* prev = &dummy;
// No special case! The head has a valid predecessor (dummy).
return dummy.next;

4. Pattern 1: Fast & Slow Pointers (Floyd's Cycle Detection)

4.1 Finding the Middle Node

slow moves 1 step, fast moves 2 steps.
When fast reaches the end (nullptr or fast->next == nullptr), slow is at the middle.

ListNode* getMiddle(ListNode* head) {
    if (!head) return nullptr;
    ListNode* slow = head;
    ListNode* fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

4.2 Mathematical Proof of Cycle Start Detection

           ◄─────── L ───────► ◄─── a ───►
  Head ───► [ 1 ] ───► [ 2 ] ───► [ 3 ] ───► [ 4 ]
                                 ▲            │
                                 │            ▼
                               [ 6 ] ◄─────── [ 5 ]
                                 ◄──── b ────►

Let:

$L$ = Distance from Head to Cycle Entrance.
$C$ = Length of Cycle ($C = a + b$).
$a$ = Distance from Cycle Entrance to Meeting Point.
$b$ = Remaining distance from Meeting Point back to Entrance ($a + b = C$).

When slow and fast meet:

$\text{Distance}_{\text{slow}} = L + a$
$\text{Distance}_{\text{fast}} = L + a + k \cdot C$ (where $k \ge 1$ complete loops)
Since fast travels at double speed: $$2(L + a) = L + a + k \cdot C \implies L + a = k \cdot C \implies L = k \cdot C - a = (k - 1)C + (C - a) = (k - 1)C + b$$

Conclusion: If one pointer starts at Head and another starts at the Meeting Point, and both move 1 step at a time, they will meet exactly at the Cycle Entrance after traveling distance $L$!

5. Pattern 2: In-Place Reversal Mechanics (Iterative & Recursive)

5.1 Iterative Reversal (3 Pointers: `prev`, `curr`, `next`)

Initial:      nullptr    [ 1 ] ──► [ 2 ] ──► [ 3 ] ──► nullptr
               ▲           ▲
              prev        curr

Step 1:       nullptr ◄── [ 1 ]     [ 2 ] ──► [ 3 ]
                            ▲         ▲
                           prev      curr

End:          nullptr ◄── [ 1 ] ◄── [ 2 ] ◄── [ 3 ]
                                                ▲
                                               prev (New Head)

ListNode* reverseList(ListNode* head) {
    ListNode* prev = nullptr;
    ListNode* curr = head;
    while (curr != nullptr) {
        ListNode* nextTemp = curr->next; // 1. Save next
        curr->next = prev;               // 2. Reverse pointer
        prev = curr;                     // 3. Advance prev
        curr = nextTemp;                 // 4. Advance curr
    }
    return prev;
}

5.2 Recursive Reversal

ListNode* reverseListRecursive(ListNode* head) {
    if (!head || !head->next) return head;
    ListNode* newHead = reverseListRecursive(head->next);
    head->next->next = head; // Make next node point back to current node
    head->next = nullptr;    // Sever forward link to prevent cycle
    return newHead;
}

6. Pattern 3: Merging & Interleaving Lists

// Merging two sorted lists iteratively with Sentinel
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
    ListNode dummy(0);
    ListNode* tail = &dummy;
    
    while (list1 && list2) {
        if (list1->val <= list2->val) {
            tail->next = list1;
            list1 = list1->next;
        } else {
            tail->next = list2;
            list2 = list2->next;
        }
        tail = tail->next;
    }
    tail->next = list1 ? list1 : list2;
    return dummy.next;
}

7. 5 Practice Problems with Detailed Solutions

Problem 1: Reverse Nodes in k-Group (LeetCode #25 - Hard)

Problem: Given the head of a linked list, reverse the nodes of the list k at a time, and return the modified list.

#include <iostream>

ListNode* reverseKGroup(ListNode* head, int k) {
    if (!head || k == 1) return head;
    
    // Check if there are at least k nodes remaining
    ListNode* check = head;
    for (int i = 0; i < k; ++i) {
        if (!check) return head; // Less than k nodes, leave as is
        check = check->next;
    }
    
    // Reverse k nodes
    ListNode* prev = nullptr;
    ListNode* curr = head;
    for (int i = 0; i < k; ++i) {
        ListNode* nextTemp = curr->next;
        curr->next = prev;
        prev = curr;
        curr = nextTemp;
    }
    
    // head is now the tail of the reversed group; attach next reversed group
    head->next = reverseKGroup(curr, k);
    return prev;
}
// Time Complexity: O(N)
// Space Complexity: O(N/k) recursive stack frames (O(1) if written fully iterative)

Problem 2: Linked List Cycle II (LeetCode #142 - Medium)

Problem: Given a linked list, return the node where the cycle begins. If there is no cycle, return nullptr.

ListNode* detectCycle(ListNode* head) {
    if (!head || !head->next) return nullptr;
    
    ListNode* slow = head;
    ListNode* fast = head;
    bool hasCycle = false;
    
    // Step 1: Detect intersection using Floyd's Tortoise and Hare
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) {
            hasCycle = true;
            break;
        }
    }
    
    if (!hasCycle) return nullptr;
    
    // Step 2: Find cycle start node
    ListNode* ptr1 = head;
    ListNode* ptr2 = slow;
    while (ptr1 != ptr2) {
        ptr1 = ptr1->next;
        ptr2 = ptr2->next;
    }
    return ptr1;
}
// Time Complexity: O(N)
// Space Complexity: O(1)

Problem 3: LRU Cache (LeetCode #146 - Medium/Hard)

Problem: Design a data structure that follows the constraints of a Least Recently Used (LRU) cache with $O(1)$ get and put.

#include <unordered_map>

class LRUCache {
private:
    struct Node {
        int key;
        int val;
        Node* prev;
        Node* next;
        Node(int k, int v) : key(k), val(v), prev(nullptr), next(nullptr) {}
    };
    
    int capacity;
    std::unordered_map<int, Node*> cache;
    Node* head; // Sentinel head
    Node* tail; // Sentinel tail
    
    void addNode(Node* node) {
        node->next = head->next;
        node->prev = head;
        head->next->prev = node;
        head->next = node;
    }
    
    void removeNode(Node* node) {
        Node* prevNode = node->prev;
        Node* nextNode = node->next;
        prevNode->next = nextNode;
        nextNode->prev = prevNode;
    }
    
    void moveToHead(Node* node) {
        removeNode(node);
        addNode(node);
    }
    
    Node* popTail() {
        Node* res = tail->prev;
        removeNode(res);
        return res;
    }

public:
    LRUCache(int cap) : capacity(cap) {
        head = new Node(0, 0);
        tail = new Node(0, 0);
        head->next = tail;
        tail->prev = head;
    }
    
    ~LRUCache() {
        Node* curr = head;
        while (curr) {
            Node* next = curr->next;
            delete curr;
            curr = next;
        }
    }
    
    int get(int key) {
        if (!cache.count(key)) return -1;
        Node* node = cache[key];
        moveToHead(node);
        return node->val;
    }
    
    void put(int key, int value) {
        if (cache.count(key)) {
            Node* node = cache[key];
            node->val = value;
            moveToHead(node);
        } else {
            Node* newNode = new Node(key, value);
            cache[key] = newNode;
            addNode(newNode);
            if (cache.size() > capacity) {
                Node* tailNode = popTail();
                cache.erase(tailNode->key);
                delete tailNode;
            }
        }
    }
};
// get(): O(1) time
// put(): O(1) time
// Space: O(Capacity)

Problem 4: Copy List with Random Pointer (LeetCode #138 - Medium)

Problem: A linked list where each node has an extra random pointer. Construct a deep copy in $O(N)$ time and $O(1)$ auxiliary space.

class NodeWithRandom {
public:
    int val;
    NodeWithRandom* next;
    NodeWithRandom* random;
    NodeWithRandom(int _val) : val(_val), next(nullptr), random(nullptr) {}
};

NodeWithRandom* copyRandomList(NodeWithRandom* head) {
    if (!head) return nullptr;
    
    // Step 1: Interleave cloned nodes: A -> A' -> B -> B' -> C -> C'
    NodeWithRandom* curr = head;
    while (curr) {
        NodeWithRandom* copy = new NodeWithRandom(curr->val);
        copy->next = curr->next;
        curr->next = copy;
        curr = copy->next;
    }
    
    // Step 2: Assign random pointers for cloned nodes
    curr = head;
    while (curr) {
        if (curr->random) {
            curr->next->random = curr->random->next;
        }
        curr = curr->next->next;
    }
    
    // Step 3: Separate original and cloned lists
    curr = head;
    NodeWithRandom* clonedHead = head->next;
    NodeWithRandom* copyCurr = clonedHead;
    
    while (curr) {
        curr->next = curr->next->next;
        if (copyCurr->next) {
            copyCurr->next = copyCurr->next->next;
        }
        curr = curr->next;
        copyCurr = copyCurr->next;
    }
    
    return clonedHead;
}
// Time Complexity: O(N)
// Auxiliary Space: O(1) (No hash map used!)

Problem 5: Palindrome Linked List (LeetCode #234 - Easy/Medium)

Problem: Check if singly linked list is a palindrome in $O(N)$ time and $O(1)$ extra space.

bool isPalindrome(ListNode* head) {
    if (!head || !head->next) return true;
    
    // 1. Find end of first half
    ListNode* slow = head;
    ListNode* fast = head;
    while (fast->next && fast->next->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    
    // 2. Reverse second half
    ListNode* prev = nullptr;
    ListNode* curr = slow->next;
    while (curr) {
        ListNode* nextTemp = curr->next;
        curr->next = prev;
        prev = curr;
        curr = nextTemp;
    }
    
    // 3. Check palindrome
    ListNode* p1 = head;
    ListNode* p2 = prev;
    bool palindrome = true;
    while (p2) {
        if (p1->val != p2->val) {
            palindrome = false;
            break;
        }
        p1 = p1->next;
        p2 = p2->next;
    }
    
    return palindrome;
}
// Time Complexity: O(N)
// Space Complexity: O(1)

8. Top 10 FAANG Interview Questions

Q1: Why is deleting a node given only a pointer to it $O(1)$ in a Singly Linked List (with a caveat)?

Answer: Copy the value of the next node into the current node (node->val = node->next->val), and rewire node->next = node->next->next. Then delete the next node. Caveat: This trick does NOT work if the node to delete is the last (tail) node of the list, because there is no successor to copy from.

Q2: How do you check if two singly linked lists intersect without extra memory?

Answer: Let lists have lengths $L_1$ and $L_2$. Traverse both to find lengths and tails. If tails differ, they don't intersect. Advance the pointer of the longer list by $|L_1 - L_2|$ steps. Then advance both pointers simultaneously; they will meet at the intersection node ($O(L_1 + L_2)$ time, $O(1)$ space).

Q3: Why is Merge Sort preferred for Linked Lists, while Quick Sort is preferred for Arrays?

Answer:

Linked lists allow $O(1)$ node insertion/merging without extra memory, making Merge Sort execute in $O(N \log N)$ time with $O(1)$ auxiliary space.
Quick Sort relies on random index access and contiguous memory cache locality for its performance, which linked lists lack.

Q4: What is memory fragmentation in linked lists, and how do custom pool allocators fix it?

Answer: Calling new for each node allocates memory from scattered heap locations, causing fragmentation and poor cache utilization. A Memory Pool (Arena Allocator) pre-allocates a large contiguous chunk of memory and assigns nodes from that pool, restoring cache locality and eliminating allocation overhead.

Q5: How do smart pointers (`std::unique_ptr` / `std::shared_ptr`) behave in linked lists?

Answer:

Using std::unique_ptr<ListNode> next can cause a stack overflow on destruction: when the head is destroyed, its destructor recursively destroys next, overflowing the call stack for long lists.
Using std::shared_ptr in doubly linked lists creates circular references (node1->next owns node2, node2->prev owns node1), causing memory leaks. prev pointers must be std::weak_ptr or raw pointers.

Q6: Can you reverse a singly linked list in a single pass?

Answer: Yes. The standard 3-pointer iterative method (prev, curr, next) reverses all pointer directions in a single forward pass with $O(N)$ time and $O(1)$ space.

Q7: How does an XOR Linked List work?

Answer: An XOR linked list is a memory-efficient doubly linked list that stores only one address field per node: $$\text{npx} = \text{address}(\text{prev}) \oplus \text{address}(\text{next})$$ Traversing forward: $\text{next} = \text{npx} \oplus \text{prev}$. It saves one pointer per node (8 bytes), but cannot be traversed without knowing the address of the preceding node and relies on non-standard pointer arithmetic.

Q8: What happens if `fast` pointer moves 3 steps instead of 2 in Floyd's cycle detection?

Answer: The relative speed between fast and slow becomes $3 - 1 = 2$ steps per iteration. If the cycle length $C$ is even, they are guaranteed to meet. If $C$ is odd and they are 1 step apart, fast could potentially jump over slow in a single step, though they will still meet in at most 2 loops. Moving 2 steps is preferred because relative speed is 1, making meeting guaranteed on the very first cycle encounter.

Q9: How to sort a linked list in $O(N \log N)$ time and $O(1)$ space?

Answer: Top-down Merge Sort:

Find middle node using fast/slow pointers and split the list into two halves.
Recursively sort left and right halves.
Merge sorted halves using Sentinel node.

Q10: How do you implement a Circular Linked List split into two equal halves?

Answer: Use fast and slow pointers. Move fast by 2 and slow by 1 until fast->next == head (odd nodes) or fast->next->next == head (even nodes). Make the second half circular: fast->next = slow->next. Make the first half circular: slow->next = head.

03-linked-lists.md

Module 03: Linked Lists — Pointer Mechanics, Reversals & Cycles

📑 Table of Contents

1. Under the Hood: Node Architecture & Memory Layout

1.1 Array vs Linked List Tradeoffs

2. C++ Implementation from Scratch (Singly & Doubly)

2.1 Singly Linked List Node

2.2 Doubly Linked List Node

3. The Sentinel (Dummy Node) Pattern

4. Pattern 1: Fast & Slow Pointers (Floyd's Cycle Detection)

4.1 Finding the Middle Node

4.2 Mathematical Proof of Cycle Start Detection

5. Pattern 2: In-Place Reversal Mechanics (Iterative & Recursive)

5.1 Iterative Reversal (3 Pointers: prev, curr, next)

5.2 Recursive Reversal

6. Pattern 3: Merging & Interleaving Lists

7. 5 Practice Problems with Detailed Solutions

Problem 1: Reverse Nodes in k-Group (LeetCode #25 - Hard)

Problem 2: Linked List Cycle II (LeetCode #142 - Medium)

Problem 3: LRU Cache (LeetCode #146 - Medium/Hard)

Problem 4: Copy List with Random Pointer (LeetCode #138 - Medium)

Problem 5: Palindrome Linked List (LeetCode #234 - Easy/Medium)

8. Top 10 FAANG Interview Questions

Q1: Why is deleting a node given only a pointer to it $O(1)$ in a Singly Linked List (with a caveat)?

Q2: How do you check if two singly linked lists intersect without extra memory?

Q3: Why is Merge Sort preferred for Linked Lists, while Quick Sort is preferred for Arrays?

Q4: What is memory fragmentation in linked lists, and how do custom pool allocators fix it?

Q5: How do smart pointers (std::unique_ptr / std::shared_ptr) behave in linked lists?

Q6: Can you reverse a singly linked list in a single pass?

Q7: How does an XOR Linked List work?

Q8: What happens if fast pointer moves 3 steps instead of 2 in Floyd's cycle detection?

Q9: How to sort a linked list in $O(N \log N)$ time and $O(1)$ space?

Q10: How do you implement a Circular Linked List split into two equal halves?

5.1 Iterative Reversal (3 Pointers: `prev`, `curr`, `next`)

Q5: How do smart pointers (`std::unique_ptr` / `std::shared_ptr`) behave in linked lists?

Q8: What happens if `fast` pointer moves 3 steps instead of 2 in Floyd's cycle detection?