DSA & Algorithms
Part 9 of 21 · DSA Interview PatternsLinked Lists — Reverse, Merge, Cycle Detection & Dummy Heads
In-place reverse, merge, Floyd cycle, and dummy-head patterns for list surgery.
- 1Gist
- 2Maps
- 3Q&A
- 4Sandbox
Voice readout needs Web Speech Synthesis in this browser.
The structure is a chain of pointers
Prefer
Rewire a constant number of pointers
Save next, point cur at prev, advance. A dummy head makes the empty-list and new-head cases the same code.
- Reverse, merge, and cycle detection are all O(n) and O(1) extra.
- The meeting point of Floyd is not automatically the cycle start.
- Recursion uses a stack the iterative form does not.
Alternative
Copy the values into an array first
Sometimes honest. It dodges the pointer question the interviewer asked.
- Overwriting next before you saved it.
- Special-casing the head instead of using a dummy.
- Stopping Floyd after the first meeting.
Save, rewire, advance
Three names: previous, current, next. Do not skip next.
- 1
Save the rest of the list
nxt = cur.next before any write. - 2
Point current backward
Or link the smaller node onto the dummy tail. - 3
Advance
prev and cur move. The dummy's next is the real head.
Overview
In-place reverse, merge, Floyd cycle, and dummy-head patterns for list surgery.
Below is the full pattern: when to reach for it, a top-down picture, runnable Python and TypeScript templates, complexity, traps, LeetCode drills, and Q&A.
When to use / recognition cues
Use pointer surgery for reverse, merge, split; Floyd for cycles; dummy heads to simplify edge cases.
Recognition cues
- reverse linked list / reverse k-group
- merge two sorted lists
- linked list cycle / find cycle start
- remove nth from end (two pointers)
Mental model
Decisions
- 1
Step 1 prev = None, cur = head - use a dummy head for merges
- nextStep 2 cur is not None?
- ?
Step 2 cur is not None?
- yesStep 3 Save nxt = cur.next
- noStep 6 New head is prev
- 3
Step 3 Save nxt = cur.next
- nextStep 4 Rewire cur.next = prev
- 4
Step 4 Rewire cur.next = prev
- nextStep 5 Advance - prev = cur, cur = nxt
- skipped step 3Failure path - rest of the list is lost
- 5
Step 5 Advance - prev = cur, cur = nxt
- nextStep 2 cur is not None?
- 6
Step 6 New head is prev
- 7
Failure path - rest of the list is lost
Lesson map
Linked Lists — Reverse, Merge, Cycle Detection & Dummy Heads
In-place reverse, merge, Floyd cycle, and dummy-head patterns for list surgery.
Architecture. Step 1 prev = None, cur = head - use a dummy head for merges Ready. Step 2 cur is not None? Ready. Step 3 Save nxt = cur.next Ready. Step 4 Rewire cur.next = prev Ready. Step 5 Advance - prev = cur, cur = nxt Ready. Step 6 New head is prev Ready. Failure path - rest of the list is lost Ready
Select a node to see why it exists, or an edge to see the protocol, direction, effect, and consequence.
Mermaid export
flowchart TB D["Step 1 prev = None, cur = head - use a dummy head for merges Ready"] C["Step 2 cur is not None? Ready"] S["Step 3 Save nxt = cur.next Ready"] R["Step 4 Rewire cur.next = prev Ready"] A["Step 5 Advance - prev = cur, cur = nxt Ready"] H["Step 6 New head is prev Ready"] F["Failure path - rest of the list is lost Ready"] D -->|continues| C C -->|yes| S S -->|continues| R R -->|continues| A A -->|continues| C C -->|no| H R -->|skipped step 3| F
Read the chart from top to bottom. Two-way decisions keep the card narrow on a phone.
Core template (Python)
Press Run. Snippets must be self-contained — no network, files, or native modules.
Core template (TypeScript)
Press Run. Snippets must be self-contained — no network, files, or native modules.
Complexity analysis
- Reverse/merge/cycle detect: O(n) time, O(1) extra space.
- Recursion reverse uses O(n) stack.
Common pitfalls & interview traps
LeetCode drill (real problems)
- Reverse Linked List
- Merge Two Sorted Lists
- Linked List Cycle
- Linked List Cycle II
- Remove Nth Node From End of List
- Reorder List
- Reverse Nodes in k-Group
Go deeper
- Back to the pattern map.
- NeetCode roadmap
- CP-Algorithms
Interview Q&A
Dummy head why?
Answer
Avoid special-casing empty/new head updates.
Floyd cycle?
Answer
Slow +1, fast +2; meet implies cycle.
Cycle start?
Answer
Reset one pointer to head; advance both +1 until meet.
Reverse k-group?
Answer
Check that k nodes remain (leave a shorter tail as is), reverse that segment, reconnect, then iterate.
Merge space?
Answer
O(1) pointer rewires if lists mutable.
Find middle?
Answer
Slow/fast; slow lands mid (even/odd variants).