In the last three chapters you learned how singly, doubly and circular linked lists are built: nodes, head, next, insertion and deletion.
Interviewers rarely ask you to just "insert a node". Instead they ask questions like:
"Reverse this linked list."
"Find the middle node in one pass."
"Does this list have a cycle? Where does the cycle start?"
"Remove the 2nd node from the end."
"Is this list a palindrome, using O(1) extra space?"
The good news is that almost all of these are solved with just two tools:
Pointer reversal: changing
nextreferences carefully, one node at a time.Fast and slow pointers: two references that move through the list at different speeds (or with a fixed gap).
Plus one small trick, the dummy node, that removes most special cases. Let's learn all three.
The Setup We Will Use
All programs in this chapter use the same Node class from the Linked List chapter, plus two small helpers: build creates a list from values, and print shows it.
class Node {
int data;
Node next;
Node(int data) {
this.data = data;
}
}static Node build(int... values) {
Node dummy = new Node(0);
Node tail = dummy;
for (int v : values) {
tail.next = new Node(v);
tail = tail.next;
}
return dummy.next;
}
static void print(Node head) {
StringBuilder sb = new StringBuilder();
for (Node cur = head; cur != null; cur = cur.next) {
sb.append(cur.data).append(" -> ");
}
System.out.println(sb.append("null"));
}Notice that build already uses a dummy node. We'll explain why later in this chapter.
Problem 1: Reverse a Linked List
Problem: Given the head of a singly linked list, reverse it and return the new head.
Input: 1 → 2 → 3 → 4 → 5 → null
Output: 5 → 4 → 3 → 2 → 1 → nullWith an array, you would swap the first and last elements and move inwards. With a singly linked list, you cannot jump to the last node, and you cannot walk backwards. So instead of moving values, we turn every arrow around.
Before: 1 → 2 → 3 → null
After: null ← 1 ← 2 ← 3The Three-Pointer Idea
We walk through the list with three references:
prev: the part we have already reversed (starts asnull).curr: the node we are reversing now (starts ashead).next: a temporary reference that remembers the rest of the list.
For each node we do four steps, in this order:
1. next = curr.next save the rest of the list
2. curr.next = prev turn the arrow around
3. prev = curr prev moves one step
4. curr = next curr moves one stepStep 1 is the important one. As soon as we do curr.next = prev, the link to the rest of the list is gone. If we had not saved it in next, we would lose the remaining nodes forever.
Step-by-Step Trace
Let's reverse 1 → 2 → 3 → null.
Start: prev = null, curr = 1
null 1 → 2 → 3 → null
Iteration 1: next = 2, 1.next = null, prev = 1, curr = 2
null ← 1 2 → 3 → null
Iteration 2: next = 3, 2.next = 1, prev = 2, curr = 3
null ← 1 ← 2 3 → null
Iteration 3: next = null, 3.next = 2, prev = 3, curr = null
null ← 1 ← 2 ← 3
curr is null → stop. Return prev (3), the new head.Recursive Reversal
Reversal can also be written recursively (see the Recursion chapter). The idea is:
Base case: an empty list or a single node is already reversed.
Recursive step: reverse everything after
head. Then the node right afterhead(which is now the tail of the reversed part) should point back tohead, andheadshould point tonull.
Trace for 1 → 2 → 3:
reverseRecursive(1)
reverseRecursive(2)
reverseRecursive(3) → base case, returns 3
back in call for 2: 2.next is 3
3.next = 2 ; 2.next = null list part: 3 → 2 → null
return 3
back in call for 1: 1.next is still 2
2.next = 1 ; 1.next = null list: 3 → 2 → 1 → null
return 3The new head (3) is found at the bottom of the recursion and simply passed back up unchanged.
Reversal in Java
class Node {
int data;
Node next;
Node(int data) {
this.data = data;
}
}
class Main {
static Node build(int... values) {
Node dummy = new Node(0);
Node tail = dummy;
for (int v : values) {
tail.next = new Node(v);
tail = tail.next;
}
return dummy.next;
}
static void print(Node head) {
StringBuilder sb = new StringBuilder();
for (Node cur = head; cur != null; cur = cur.next) {
sb.append(cur.data).append(" -> ");
}
System.out.println(sb.append("null"));
}
// Iterative reversal: O(n) time, O(1) extra space
static Node reverse(Node head) {
Node prev = null;
Node curr = head;
while (curr != null) {
Node next = curr.next; // 1. save the rest of the list
curr.next = prev; // 2. reverse the link
prev = curr; // 3. move prev forward
curr = next; // 4. move curr forward
}
return prev; // prev is the new head
}
// Recursive reversal: O(n) time, O(n) call-stack space
static Node reverseRecursive(Node head) {
if (head == null || head.next == null) {
return head; // empty list or last node
}
Node newHead = reverseRecursive(head.next);
head.next.next = head; // the node after head now points back to head
head.next = null; // head becomes the tail
return newHead;
}
public static void main(String[] args) {
Node head = build(1, 2, 3, 4, 5);
System.out.print("Original: ");
print(head);
head = reverse(head);
System.out.print("Reversed: ");
print(head);
head = reverseRecursive(head);
System.out.print("Reversed again: ");
print(head);
System.out.print("Single node: ");
print(reverse(build(7)));
System.out.print("Empty list: ");
print(reverse(null));
}
}Output:
Original: 1 -> 2 -> 3 -> 4 -> 5 -> null
Reversed: 5 -> 4 -> 3 -> 2 -> 1 -> null
Reversed again: 1 -> 2 -> 3 -> 4 -> 5 -> null
Single node: 7 -> null
Empty list: nullAlways test the two edge cases at the bottom (one node, empty list). The iterative version handles both without any extra if.
Version | Time | Extra space | Notes |
|---|---|---|---|
Iterative |
|
| Preferred in interviews and production |
Recursive |
|
| Elegant, but a very long list can cause |
Problem 2: Reverse Part of a List
Problem: Reverse only the nodes from position left to position right (1-based).
Input: 1 → 2 → 3 → 4 → 5, left = 2, right = 4
Output: 1 → 4 → 3 → 2 → 5We reuse the same reversal loop, but only for right - left + 1 nodes. Then we reconnect the reversed part to the nodes on both sides.
before = node at position left - 1 (here: 1)
Reverse 2 → 3 → 4 :
prev = 4 (new head of the part)
curr = 5 (first node after the part)
node 2 is now the tail of the part
Reconnect:
2.next = 5 (before.next.next = curr)
1.next = 4 (before.next = prev)
Result: 1 → 4 → 3 → 2 → 5What if left = 1? Then there is no node before the part. Instead of writing special code for that case, we put a dummy node in front of the head. That brings us to the next idea.
The Dummy Node Trick
A dummy node (also called a sentinel) is a fake node placed before the real head:
dummy → 1 → 2 → 3 → nullIts value does not matter. It guarantees that every real node has a node before it, even the head. So "delete the head" or "insert before the head" become ordinary operations. At the end, the real head is simply dummy.next.
Use a dummy node whenever the head itself might change: deleting nodes, reversing a part that may start at the head, or building a new list (such as merging two sorted lists).
Merge two sorted lists is a classic example (you saw merging of arrays in the Merge Sort chapter). We keep a tail pointer and always attach the smaller front node. The program below contains both reverseBetween from Problem 2 and merge:
class Node {
int data;
Node next;
Node(int data) {
this.data = data;
}
}
class Main {
static Node build(int... values) {
Node dummy = new Node(0);
Node tail = dummy;
for (int v : values) {
tail.next = new Node(v);
tail = tail.next;
}
return dummy.next;
}
static void print(Node head) {
StringBuilder sb = new StringBuilder();
for (Node cur = head; cur != null; cur = cur.next) {
sb.append(cur.data).append(" -> ");
}
System.out.println(sb.append("null"));
}
// Reverse only the nodes from position left to right (1-based)
static Node reverseBetween(Node head, int left, int right) {
Node dummy = new Node(0);
dummy.next = head;
Node before = dummy;
for (int i = 1; i < left; i++) {
before = before.next; // node just before position left
}
Node prev = null;
Node curr = before.next;
for (int i = left; i <= right; i++) {
Node next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
// before.next is the old first node of the part, now its last node
before.next.next = curr; // connect the part's tail to the rest
before.next = prev; // connect the front to the part's new head
return dummy.next;
}
// Merge two sorted lists using a dummy node
static Node merge(Node a, Node b) {
Node dummy = new Node(0);
Node tail = dummy;
while (a != null && b != null) {
if (a.data <= b.data) {
tail.next = a;
a = a.next;
} else {
tail.next = b;
b = b.next;
}
tail = tail.next;
}
tail.next = (a != null) ? a : b; // attach whatever is left
return dummy.next;
}
public static void main(String[] args) {
System.out.print("Reverse positions 2..4: ");
print(reverseBetween(build(1, 2, 3, 4, 5), 2, 4));
System.out.print("Reverse positions 1..5: ");
print(reverseBetween(build(1, 2, 3, 4, 5), 1, 5));
System.out.print("Merged: ");
print(merge(build(1, 4, 7), build(2, 3, 8, 9)));
}
}Output:
Reverse positions 2..4: 1 -> 4 -> 3 -> 2 -> 5 -> null
Reverse positions 1..5: 5 -> 4 -> 3 -> 2 -> 1 -> null
Merged: 1 -> 2 -> 3 -> 4 -> 7 -> 8 -> 9 -> nullThe second line reverses from position 1, which changes the head. Thanks to the dummy node, the same code handles it. The merge runs in O(n + m) time and O(1) extra space, because it reuses the existing nodes instead of creating new ones.
Fast and Slow Pointers
In the Two Pointers chapter, you used slow and fast indexes on arrays. On linked lists, the same idea becomes even more powerful, because we cannot use indexes or know the length in advance.
Fast and slow pointers (also called the tortoise and hare technique): two references start at the head; the slow one moves 1 node per step and the fast one moves 2 nodes per step. Because their speeds differ, their positions reveal facts about the list's structure.
The basic loop always looks like this:
Node slow = head;
Node fast = head;
while (fast != null && fast.next != null) {
slow = slow.next; // 1 step
fast = fast.next.next; // 2 steps
}The condition fast != null && fast.next != null is essential. Since fast jumps two nodes, we must check both before using fast.next.next, otherwise we get a NullPointerException.
Problem 3: Find the Middle Node
The naive way is two passes: count the nodes, then walk n / 2 steps. With fast and slow pointers we need only one pass.
When fast reaches the end, it has travelled twice as far as slow, so slow is in the middle.
Odd length (1 → 2 → 3 → 4 → 5):
Step 0: slow = 1, fast = 1
Step 1: slow = 2, fast = 3
Step 2: slow = 3, fast = 5
fast.next is null → stop. Middle = 3Even length (1 → 2 → 3 → 4 → 5 → 6):
Step 0: slow = 1, fast = 1
Step 1: slow = 2, fast = 3
Step 2: slow = 3, fast = 5
Step 3: slow = 4, fast = null (5 → 6 → null)
fast is null → stop. Middle = 4For an even length there are two middle nodes (3 and 4). This loop returns the second middle. If a problem wants the first middle (for example, to split a list into two halves for merge sort), change the condition:
// First middle (head must not be null)
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}For 1 → 2 → 3 → 4 → 5 → 6 this stops with slow = 3; for odd lengths both versions give the same answer.
Problem 4: Detect a Cycle (Floyd's Algorithm)
A linked list has a cycle if some node's next points back to an earlier node. Then a normal traversal never reaches null and loops forever.
1 → 2 → 3 → 4 → 5 → 6
↑ │
└───────────────┘ (6.next = 3)This is different from a circular linked list, where the last node deliberately points to the head. Here the cycle is usually a bug or a puzzle, and it may start anywhere.
Floyd's cycle detection uses the same slow/fast loop:
If there is no cycle,
fastreachesnulland we returnfalse.If there is a cycle, both pointers eventually go round it, and
fastcatches up withslow. Whenslow == fast(the same node object), we returntrue.
static boolean hasCycle(Node head) {
Node slow = head;
Node fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
return true;
}
}
return false;
}Why Can't Fast Jump Over Slow?
Once both pointers are inside the cycle, think of the distance from fast forward to slow. In each step, slow moves 1 ahead and fast moves 2 ahead, so the gap shrinks by exactly 1:
gap: 3 → 2 → 1 → 0 (they meet)A gap that shrinks by 1 every step must hit 0 exactly; it cannot skip from 1 to -1. And since the gap is less than the cycle length when slow enters the cycle, they meet before slow finishes one full loop. So the algorithm takes O(n) time and only O(1) extra space.
Let's trace the list above:
Step 0: slow = 1, fast = 1
Step 1: slow = 2, fast = 3
Step 2: slow = 3, fast = 5
Step 3: slow = 4, fast = 3 (5 → 6 → 3)
Step 4: slow = 5, fast = 5 → they meet at node 5. Cycle!A simpler idea is to store every visited node in a set and stop when you see a node again. That also works in O(n) time, but needs O(n) extra space. (You will learn about HashSet later.) Floyd's algorithm is the answer interviewers expect because it uses O(1) space.
Problem 5: Find Where the Cycle Starts
This is the famous follow-up. After slow and fast meet:
Put a new pointer
pat the head.Move
pandslowone step at a time.The node where they meet is the start of the cycle.
Why Does This Work?
Let:
a= number of steps from the head to the cycle startb= number of steps from the cycle start to the meeting point (inside the cycle)c= length of the cycle
head ──a steps──→ start ──b steps──→ meeting point
↑ │
└──── c - b steps ─────┘When they meet:
slow has walked: a + b
fast has walked: 2(a + b) (twice as fast)
fast also equals slow's distance plus some full loops:
2(a + b) = a + b + k·c (k ≥ 1)
a + b = k·c
a = k·c - b
a = (k - 1)·c + (c - b)The last line says: walking a steps from the meeting point is the same as walking c - b steps (which reaches the cycle start) plus some whole loops (which come back to the same place). So a pointer starting at the head and a pointer starting at the meeting point, both moving 1 step at a time, arrive at the cycle start at the same time.
Check with our example: head is 1, cycle start is 3, so a = 2. The cycle is 3 → 4 → 5 → 6 → 3, so c = 4. They met at node 5, so b = 2. Then a + b = 4 = 1 · c with k = 1, and c - b = 2 = a. Phase 2:
p = 1, slow = 5
p = 2, slow = 6
p = 3, slow = 3 → cycle starts at node 3static Node cycleStart(Node head) {
Node slow = head;
Node fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
Node p = head; // phase 2
while (p != slow) {
p = p.next;
slow = slow.next;
}
return p;
}
}
return null;
}Cycle length: after the meeting, keep one pointer fixed and walk the other around the cycle until it comes back, counting the steps. For our example the answer is 4.
Problem 6: Remove the N-th Node from the End
This uses two pointers moving at the same speed but with a fixed gap between them.
The idea: move fast ahead by n nodes first. Then move both together. When fast reaches the last node, slow is exactly n nodes behind it, which is just before the node we want to delete.
We start both at a dummy node, so deleting the head works too.
List: dummy → 10 → 20 → 30 → 40 → 50, n = 2 (delete 40)
Move fast 2 steps: slow = dummy, fast = 20
Move both until fast.next == null:
slow = 10, fast = 30
slow = 20, fast = 40
slow = 30, fast = 50 (fast.next is null, stop)
slow.next = slow.next.next → 30 now points to 50
Result: 10 → 20 → 30 → 50With n = 5, fast reaches 50 immediately, slow stays at the dummy, and the head (10) is removed. No special case needed.
static Node removeNthFromEnd(Node head, int n) {
Node dummy = new Node(0);
dummy.next = head;
Node fast = dummy;
Node slow = dummy;
for (int i = 0; i < n; i++) { // create a gap of n nodes
fast = fast.next;
}
while (fast.next != null) { // move both until fast is at the last node
fast = fast.next;
slow = slow.next;
}
slow.next = slow.next.next; // slow is just before the node to delete
return dummy.next;
}This assumes 1 ≤ n ≤ length, as the problem usually guarantees. It finishes in a single pass.
Problem 7: Palindrome Linked List
Problem: Check whether a list reads the same forwards and backwards, using O(1) extra space.
1 → 2 → 3 → 2 → 1 → true
1 → 2 → 2 → 1 → true
1 → 2 → 3 → falseCopying the values into an array would be easy but uses O(n) space. Instead, we combine the two tools from this chapter:
Find the middle with fast and slow pointers.
Reverse the second half.
Compare the first half and the reversed second half node by node.
Reverse the second half again to restore the list (good manners: don't damage the caller's data).
1 → 2 → 3 → 2 → 1
↑ middle
After reversing from the middle:
first half: 1 → 2 → 3
second half: 1 → 2 → 3 → null (reversed)
Compare: 1=1, 2=2, 3=3 → palindromeWe stop when the second-half pointer reaches null. For odd lengths, the middle node is compared with itself, which is harmless.
Complete Program: Fast and Slow Pointer Problems
class Node {
int data;
Node next;
Node(int data) {
this.data = data;
}
}
class Main {
static Node build(int... values) {
Node dummy = new Node(0);
Node tail = dummy;
for (int v : values) {
tail.next = new Node(v);
tail = tail.next;
}
return dummy.next;
}
static void print(Node head) {
StringBuilder sb = new StringBuilder();
for (Node cur = head; cur != null; cur = cur.next) {
sb.append(cur.data).append(" -> ");
}
System.out.println(sb.append("null"));
}
static Node reverse(Node head) {
Node prev = null;
Node curr = head;
while (curr != null) {
Node next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}
// Middle node (second middle when the length is even)
static Node middle(Node head) {
Node slow = head;
Node fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
// Floyd's cycle detection
static boolean hasCycle(Node head) {
Node slow = head;
Node fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
return true;
}
}
return false;
}
// Returns the first node of the cycle, or null if there is no cycle
static Node cycleStart(Node head) {
Node slow = head;
Node fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
Node p = head; // phase 2
while (p != slow) {
p = p.next;
slow = slow.next;
}
return p;
}
}
return null;
}
// Number of nodes in the cycle (0 if there is no cycle)
static int cycleLength(Node head) {
Node slow = head;
Node fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
int length = 1;
Node cur = slow.next;
while (cur != slow) {
length++;
cur = cur.next;
}
return length;
}
}
return 0;
}
// Remove the n-th node from the end (1-based), one pass
static Node removeNthFromEnd(Node head, int n) {
Node dummy = new Node(0);
dummy.next = head;
Node fast = dummy;
Node slow = dummy;
for (int i = 0; i < n; i++) { // create a gap of n nodes
fast = fast.next;
}
while (fast.next != null) { // move both until fast is at the last node
fast = fast.next;
slow = slow.next;
}
slow.next = slow.next.next; // slow is just before the node to delete
return dummy.next;
}
// Palindrome check in O(n) time and O(1) extra space
static boolean isPalindrome(Node head) {
Node secondHalf = reverse(middle(head));
Node p1 = head;
Node p2 = secondHalf;
boolean result = true;
while (p2 != null) {
if (p1.data != p2.data) {
result = false;
break;
}
p1 = p1.next;
p2 = p2.next;
}
reverse(secondHalf); // restore the original list
return result;
}
public static void main(String[] args) {
System.out.println("Middle of 1..5: " + middle(build(1, 2, 3, 4, 5)).data);
System.out.println("Middle of 1..6: " + middle(build(1, 2, 3, 4, 5, 6)).data);
// Build 1 -> 2 -> 3 -> 4 -> 5 -> 6 and link 6 back to 3
Node head = build(1, 2, 3, 4, 5, 6);
Node third = head.next.next;
Node last = third.next.next.next;
last.next = third;
System.out.println("Has cycle: " + hasCycle(head));
System.out.println("Cycle starts at: " + cycleStart(head).data);
System.out.println("Cycle length: " + cycleLength(head));
System.out.println("Has cycle (1..5): " + hasCycle(build(1, 2, 3, 4, 5)));
System.out.print("Remove 2nd from end: ");
print(removeNthFromEnd(build(10, 20, 30, 40, 50), 2));
System.out.print("Remove 5th from end: ");
print(removeNthFromEnd(build(10, 20, 30, 40, 50), 5));
Node pal = build(1, 2, 3, 2, 1);
System.out.println("1 2 3 2 1 palindrome: " + isPalindrome(pal));
System.out.println("1 2 2 1 palindrome: " + isPalindrome(build(1, 2, 2, 1)));
System.out.println("1 2 3 palindrome: " + isPalindrome(build(1, 2, 3)));
System.out.print("List after check: ");
print(pal);
}
}Output:
Middle of 1..5: 3
Middle of 1..6: 4
Has cycle: true
Cycle starts at: 3
Cycle length: 4
Has cycle (1..5): false
Remove 2nd from end: 10 -> 20 -> 30 -> 50 -> null
Remove 5th from end: 20 -> 30 -> 40 -> 50 -> null
1 2 3 2 1 palindrome: true
1 2 2 1 palindrome: true
1 2 3 palindrome: false
List after check: 1 -> 2 -> 3 -> 2 -> 1 -> nullNotice that we never call print on the list with a cycle. Printing it would loop forever, which is exactly the problem cycle detection protects us from.
Time and Space Complexity
Problem | Technique | Time | Extra space |
|---|---|---|---|
Reverse a list | Three pointers |
|
|
Reverse a list (recursive) | Recursion |
|
|
Reverse positions left..right | Dummy + three pointers |
|
|
Merge two sorted lists | Dummy + tail |
|
|
Middle node | Fast and slow |
|
|
Detect cycle | Floyd (fast and slow) |
|
|
Cycle start / length | Floyd + second phase |
|
|
Remove n-th from end | Gap of n + dummy |
|
|
Palindrome list | Middle + reverse |
|
|
Which Technique Should I Use?
If the problem says... | Think of... |
|---|---|
"reverse", "in reverse order", "reverse in groups" | Three-pointer reversal |
"middle", "split into two halves" | Fast and slow pointers |
"cycle", "loop", "does it end?" | Floyd's algorithm |
"k-th from the end", "one pass" | Two pointers with a gap of k |
"palindrome", "compare first half with second half" | Middle + reverse second half |
The head might be deleted or changed | Dummy node |
Common Mistakes
1. Losing the rest of the list
Writing curr.next = prev before saving curr.next cuts the list, and the remaining nodes are lost. Always save next first.
2. Returning the wrong head after reversal
When the loop ends, curr is null. The new head is prev. Also remember to use the returned value: head = reverse(head);. Calling reverse(head) and continuing to use the old head leaves you with a one-node list.
3. Wrong loop condition for fast
Checking only fast != null crashes on fast.next.next for odd-length lists (including a single node): fast lands on the last node, fast.next is null, and null.next throws a NullPointerException. Use fast != null && fast.next != null.
4. Comparing values instead of nodes in cycle detection
Use slow == fast (same node object), not slow.data == fast.data. Two different nodes can hold the same value.
5. Checking for the meeting before moving
Both pointers start at head, so slow == fast is true at the start. Move first, then compare.
6. Forgetting the head-deletion case
Deleting the first node, or reversing from position 1, changes the head. Without a dummy node you need special if statements, and they are easy to get wrong.
7. Forgetting the recursion limit
Recursive reversal uses one stack frame per node. For lists with hundreds of thousands of nodes, the iterative version is the safe choice.
Interview Tips
Draw the boxes and arrows. Linked list bugs are almost always about the order of pointer updates. Drawing three or four nodes and updating arrows by hand catches them quickly.
Test four cases out loud: empty list, one node, two nodes, and a normal list (odd and even lengths for middle-based problems).
Write iterative reversal from memory. It is a building block for harder problems: reverse in groups of k, reorder list, add two numbers stored in reverse, and palindrome list.
Be ready to prove Floyd's algorithm. "The gap shrinks by one each step, so they must meet" and the equation
a = (k - 1)c + (c - b)are what interviewers look for.Mention the space trade-off. A set of visited nodes or an array copy works, but uses
O(n)extra space. The pointer techniques useO(1).Ask whether you may modify the list. If not, restore it (as in our palindrome solution) or use extra space.
Practice Problems
Reverse Linked List
Reverse Linked List II (reverse between positions)
Middle of the Linked List
Linked List Cycle
Linked List Cycle II (find the start)
Remove Nth Node From End of List
Palindrome Linked List
Merge Two Sorted Lists
Reorder List (middle + reverse + merge)
Reverse Nodes in k-Group (hard)
The Main Idea
Most linked list interview problems are built from a few small, reusable moves:
Reverse: next = curr.next; curr.next = prev; prev = curr; curr = next;
Middle: slow += 1, fast += 2, until fast reaches the end
Cycle: slow += 1, fast += 2, a meeting means a cycle
Cycle start: restart one pointer at head, move both by 1, meet at start
K-th from end: give fast a head start of k, then move both by 1
Dummy node: put a fake node before head so the head is never specialSave the next node before you change a link, let a fast pointer explore ahead of a slow one, and put a dummy node in front of the head. With these three habits, most linked list problems become short, O(1)-space solutions.