Blind 75 — Linked List Pattern Guide

How to Identify a “Linked List” Problem

Interview Triggers

• Input given as ListNode head
• “Reverse”, “reorder”, “rotate”
• “Detect a cycle”
• “Find the middle / Nth from end”
• “Merge two / K sorted lists”
• “Remove the …th node”

Which Sub-Pattern Does It Belong To?

If the prompt says…	Use this sub-pattern	Example LC
Reverse the whole list	Iterative pointer flip	206
Detect a cycle	Floyd’s slow/fast	141
Merge two sorted lists	Dummy head + two pointers	21
Merge K sorted lists	Min-heap of heads / divide & conquer	23
Remove Nth node from end	Two pointers with N-gap	19
Reorder list (L0→Ln→L1→Ln-1…)	Find mid + reverse + zip	143

---

The Decision Tree

LINKED LIST PROBLEM
│
├─ Need cycle / mid / k-from-end?
│   └─ Slow/Fast (Floyd's) pointers → LC 141, 876, 19
│
├─ Need to flip pointer direction?
│   └─ Iterative reversal (prev, curr, next) → LC 206
│
├─ Merging?
│   ├─ Two sorted lists           → Dummy + two pointers (LC 21)
│   └─ K sorted lists             → Min-heap of heads (LC 23)
│
└─ Reorder / partition?
    └─ Find mid → reverse second half → interleave (LC 143)

---

The Three Foundational Templates

Reverse a Linked List

ListNode prev = null, curr = head;
while (curr != null) {
    ListNode next = curr.next;
    curr.next = prev;
    prev = curr;
    curr = next;
}
return prev;

Floyd’s Cycle Detection

ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow == fast) return true;
}
return false;

Find Middle Node

ListNode slow = head, fast = head;
while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; }
return slow;   // for even length, slow is the second middle

---

Bread & Butter Problems

#	Problem	LC #	Difficulty	Sub-Pattern
1	Reverse Linked List	206	Easy	Iterative flip
2	Linked List Cycle	141	Easy	Floyd’s slow/fast
3	Merge Two Sorted Lists	21	Easy	Dummy + two pointers
4	Remove Nth Node From End	19	Medium	Two pointers + gap

FAANG “Aha!” Problems

#	Problem	LC #	Difficulty	Sub-Pattern
1	Reorder List	143	Medium	Mid + reverse + zip
2	Merge K Sorted Lists	23	Hard	Min-heap of heads

---

Java Implementation Tips

• ALWAYS use a dummy head when the output’s head might change (insert/remove at head).
• After detaching nodes, set the old .next = null to prevent stale links / cycles.
• Java has no built-in ListNode — re-declare in scope: class ListNode { int val; ListNode next; }.
• For Floyd’s, prefer while (fast != null && fast.next != null) — order matters to avoid NPE.
• Recursion depth: list of 10^5 nodes can blow the Java stack — prefer iterative for long lists.

---

Senior Mental Trigger

“Head might change → dummy node. Find position → slow/fast. Reverse → 3 pointer dance (prev, curr, next).”