Linked Lists

```cpp // Singly linked list node struct ListNode { int val; ListNode* next; ListNode(int x) : val(x), next(nullptr) {} }; // Doubly linked list node (for LRU Cache, deque) struct DListNode { int key, val; DListNode* prev; DListNode* next; DListNode(int k, int v) : key(k), val(v), prev(nullptr), next(nullptr) {} }; ```

Fast/Slow pointer templates ```cpp // Find middle — slow stops at middle ListNode *slow = head, *fast = head; while (fast && fast->next) { slow = slow->next; fast = fast->next->next; } // slow = middle (left-middle for even length)

// Cycle detection (Floyd’s) ListNode *slow = head, *fast = head; while (fast && fast->next) { slow = slow->next; fast = fast->next->next; if (slow == fast) return true; // cycle detected } return false;

// Kth node from end (two-pointer with gap k) ListNode *fast = head, *slow = head; for (int i = 0; i < k; i++) fast = fast->next; // advance fast by k while (fast) { slow = slow->next; fast = fast->next; } // slow = kth node from end

</div>
<div class="ch-cplx-row">
  <span class="ch-cplx"><span>Time</span>O(n)</span>
  <span class="ch-cplx"><span>Space</span>O(1)</span>
</div>
</div>
<div class="chapter-section">
<h2 class="section-heading">Section 3 — Pattern: Reversal</h2>
<p>Reversing a linked list is O(n) time, O(1) space. Requires tracking three pointers: prev, curr, and next.</p>
<div class="insight-box">
  <span class="insight-label">The 3-Pointer Dance</span>
  Before breaking the link curr→next, save next first. Then redirect curr→prev. Advance: prev=curr, curr=next. Repeat until curr=nullptr. Return prev (new head).
</div>
<div class="ch-code-wrap">
```cpp
// Reverse entire list — iterative (preferred)
ListNode* reverseList(ListNode* head) {
    ListNode *prev = nullptr, *curr = head;
    while (curr) {
        ListNode* nxt = curr->next;   // save next
        curr->next = prev;            // redirect
        prev = curr;                  // advance prev
        curr = nxt;                   // advance curr
    }
    return prev; // new head
}
// Reverse a sublist from position left to right
// (0-indexed) — use dummy node + find boundaries
ListNode dummy(0); dummy.next = head;
ListNode* pre = &dummy;
for (int i = 0; i < left-1; i++) pre = pre->next; // node before sublist
ListNode* curr = pre->next;
for (int i = 0; i < right-left; i++) {
    ListNode* nxt = curr->next;
    curr->next = nxt->next;
    nxt->next = pre->next;
    pre->next = nxt;
}
return dummy.next;

```cpp // Remove nth node from end — dummy + two pointers ListNode dummy(0); dummy.next = head; ListNode *fast = &dummy, *slow = &dummy; for (int i = 0; i <= n; i++) fast = fast->next; // gap of n+1 while (fast) { slow = slow->next; fast = fast->next; } slow->next = slow->next->next; // remove target return dummy.next;

// Delete node with specific value — dummy prevents head case ListNode dummy(0); dummy.next = head; ListNode* curr = &dummy; while (curr->next) { if (curr->next->val == val) curr->next = curr->next->next; else curr = curr->next; } return dummy.next;

</div>
</div>
<div class="chapter-section">
<h2 class="section-heading">Section 5 — Pattern: Merge Two Sorted Lists</h2>
<p>Compare heads of both lists. Take the smaller one, advance that pointer. Use a dummy node to avoid edge cases.</p>
<div class="ch-code-wrap">
```cpp
// Merge two sorted linked lists — O(m+n) time, O(1) space
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 remaining
return dummy.next;

```cpp // Reorder List — O(n) time, O(1) space 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, *curr = slow->next; slow->next = nullptr; // cut list at middle while (curr) { ListNode* nxt = curr->next; curr->next = prev; prev = curr; curr = nxt; } // 3. Interleave first half and reversed second half ListNode *first = head, *second = prev; while (second) { ListNode *fn = first->next, *sn = second->next; first->next = second; second->next = fn; first = fn; second = sn; } } ```