DSA Patterns Made Simple · Linked Lists, Stacks and Intervals
Reversing and Merging Linked Lists
Three pointers (previous, current, next) reverse a list in place, and a dummy head node makes building or merging lists free of special cases.
The problem
Reverse Linked List: turn 1 -> 2 -> 3 -> 4 into 4 -> 3 -> 2 -> 1 without creating new nodes. It's one of the most-asked warm-up questions, and the pointer juggling trips people up under pressure.
How to spot it
- "Reverse" a list or part of it (reverse between positions, reverse in groups of k)
- "Merge" two sorted lists, "partition" a list, "add two numbers" stored as lists
- Any time you build a new list node by node
- Palindrome linked list (reverse the second half, then compare)
The idea
Reversal: walk the list and flip each arrow to point backwards. You need three names at each step: prev (the already-reversed part), cur (the node being flipped) and nxt (saved so you don't lose the rest of the list). Picture flipping a line of people to face the other way: before you turn someone around, remember who was in front of them.
Dummy head: when building a list, start with a fake node and keep a tail pointer. Append by setting tail.next, then return dummy.next. No "is the list empty yet?" checks.
The template
prev, cur = None, head
while cur:
nxt = cur.next # 1. remember the rest
cur.next = prev # 2. flip the arrow
prev = cur # 3. step forward
cur = nxt
return prev # the new head
let prev = null, cur = head;
while (cur) {
const nxt = cur.next; // 1. remember the rest
cur.next = prev; // 2. flip the arrow
prev = cur; // 3. step forward
cur = nxt;
}
return prev; // the new head
Say it out loud while you code: save next, flip, step, step.
Worked example
Reverse a list, merge two sorted lists with a dummy head, and check whether a list is a palindrome by reversing its second half.
class Node:
def __init__(self, val, next=None):
self.val, self.next = val, next
def build(values):
head = None
for v in reversed(values):
head = Node(v, head)
return head
def show(head):
out = []
while head:
out.append(str(head.val))
head = head.next
return " -> ".join(out)
def reverse(head):
prev, cur = None, head
while cur:
nxt = cur.next
cur.next = prev
prev, cur = cur, nxt
return prev
def merge(a, b):
dummy = tail = Node(0)
while a and b:
if a.val <= b.val:
tail.next, a = a, a.next
else:
tail.next, b = b, b.next
tail = tail.next
tail.next = a or b # one list may have nodes left
return dummy.next
def is_palindrome(head):
slow = fast = head
while fast and fast.next: # find the middle (previous lesson)
slow, fast = slow.next, fast.next.next
second = reverse(slow)
first = head
while second:
if first.val != second.val:
return False
first, second = first.next, second.next
return True
print(show(reverse(build([1, 2, 3, 4]))))
print(show(merge(build([1, 2, 4]), build([1, 3, 4, 5]))))
print("1 2 2 1 palindrome?", is_palindrome(build([1, 2, 2, 1])))
print("1 2 3 palindrome?", is_palindrome(build([1, 2, 3])))
Output
4 -> 3 -> 2 -> 1 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 1 2 2 1 palindrome? True 1 2 3 palindrome? False
class Node {
constructor(val, next = null) { this.val = val; this.next = next; }
}
function build(values) {
let head = null;
for (const v of [...values].reverse()) head = new Node(v, head);
return head;
}
function show(head) {
const out = [];
for (; head; head = head.next) out.push(head.val);
return out.join(" -> ");
}
function reverse(head) {
let prev = null, cur = head;
while (cur) {
const nxt = cur.next;
cur.next = prev;
prev = cur;
cur = nxt;
}
return prev;
}
function merge(a, b) {
const dummy = new Node(0);
let tail = dummy;
while (a && b) {
if (a.val <= b.val) { tail.next = a; a = a.next; }
else { tail.next = b; b = b.next; }
tail = tail.next;
}
tail.next = a ?? b; // one list may have nodes left
return dummy.next;
}
function isPalindrome(head) {
let slow = head, fast = head;
while (fast && fast.next) { slow = slow.next; fast = fast.next.next; }
let second = reverse(slow), first = head;
while (second) {
if (first.val !== second.val) return false;
first = first.next; second = second.next;
}
return true;
}
const py = (b) => (b ? "True" : "False");
console.log(show(reverse(build([1, 2, 3, 4]))));
console.log(show(merge(build([1, 2, 4]), build([1, 3, 4, 5]))));
console.log("1 2 2 1 palindrome?", py(isPalindrome(build([1, 2, 2, 1]))));
console.log("1 2 3 palindrome?", py(isPalindrome(build([1, 2, 3]))));
Output
4 -> 3 -> 2 -> 1 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 1 2 2 1 palindrome? True 1 2 3 palindrome? False
Common mistakes
- Losing the rest of the list. Overwrite
cur.nextonly after saving it innxt. - Returning
headafter reversing. The old head is now the tail; returnprev. - Forgetting leftovers when merging. When one list runs out, attach the rest of the other in one step.
- Recursion depth. A recursive reversal is elegant but uses O(n) stack; a 100,000-node list can overflow it.
Practice
- Reverse Linked List (easy)
- Merge Two Sorted Lists (easy)
Key points
- Reverse with three pointers: save next, flip, step, step.
- A dummy head + tail pointer builds lists without special cases; return
dummy.next. - Many list problems combine patterns: middle (fast/slow) + reverse + compare.
- In-place pointer work is O(n) time and O(1) space.
Practice questions
Walk through reversing a linked list iteratively.
Answer
Keep prev = null and cur = head. While cur exists: save nxt = cur.next, point cur.next at prev, move prev to cur and cur to nxt. When cur is null, prev is the new head. O(n) time, O(1) space.
What is a dummy (sentinel) node, and why use it?
Answer
A placeholder node placed before the real head. Building or editing the list through it means the first real node is handled like any other (no 'if head is None' branches), and the answer is dummy.next.
Open in the app to mark lessons complete, take notes and track your progress.