Eine verkettete Liste umkehren
Das kanonische Zeiger-Problem: eine Liste mit drei Zeigern an Ort und Stelle neu verknüpfen - iterativ und rekursiv.
Deutsche Übersetzung in Arbeit
Diese Lektion ist noch nicht ins Deutsche übersetzt und wird daher auf Englisch angezeigt. Der Rest der Seite ist vollständig lokalisiert.
Auf dieser Seite
"Reverse a linked list" is the single most common linked-list interview question, and a building
block for dozens of harder ones. It's pure pointer surgery: no extra data structure, just carefully
re-threading the next references one node at a time. Master this and you've mastered the technique.
Three pointers, one pass
To reverse in place, walk the list flipping each node's next to point backward. The catch: the
moment you flip a pointer, you lose your way forward - so you must save the next node first. Three
references keep you oriented: prev (the reversed part behind you), curr (the node you're
flipping), and a saved next.
// reverse a linked list in place — O(n) time, O(1) space
ListNode reverse(ListNode head) {
ListNode prev = null; // reversed portion starts empty
ListNode curr = head;
while (curr != null) {
ListNode next = curr.next; // 1. save the way forward
curr.next = prev; // 2. flip this node's pointer backward
prev = curr; // 3. advance prev
curr = next; // 4. advance curr
}
return prev; // prev is the new head
}Trace 1 → 2 → 3: after the first iteration 1 points to null and prev is 1; after the second,
2 → 1; after the third, 3 → 2 → 1. When curr falls off the end, prev holds the new head. The
whole dance is O(n) time, O(1) space - it never allocates a node.
The recursive version
The same reversal reads elegantly as recursion: reverse everything after the head, then fix the two pointers between the head and its old successor.
ListNode reverseRecursive(ListNode head) {
if (head == null || head.next == null) return head; // base case
ListNode newHead = reverseRecursive(head.next); // reverse the rest
head.next.next = head; // make the successor point back to head
head.next = null; // head becomes the new tail
return newHead;
}It's clean, but remember the lesson from complexity: recursion here is O(n) space because the call stack goes n deep. For a very long list the iterative version is safer - it can't overflow the stack.
Reversal is a sub-step, not just a problem
Many harder problems use reversal as one step: reversing a sublist between positions m and n, reversing nodes in groups of k, or checking a palindrome linked list (reverse the second half and compare). Once the three-pointer flip is automatic, these become "find the boundary, then reverse this part."
A line of people each hold the hand of the person ahead. To reverse the line without anyone letting
go and getting lost, each person must first note who's ahead of them, then turn to grip the person
who was behind instead. Do it one person at a time, front to back, and the line flips direction in a
single pass - nobody wanders off because everyone remembered their 'next' before switching grips.
That saved reference is exactly the next pointer you stash before flipping.
Reverse the nodes of a linked list from position m to position n (1-indexed), leaving the rest untouched, in one pass. Describe how you'd adapt the three-pointer reversal, and why a dummy head helps.
Why must you save curr.next before flipping curr.next = prev when reversing a list?
Key takeaways
- Reversing a linked list in place uses three pointers - prev, curr, and a saved next - and one pass, O(n) time, O(1) space.
- Always save curr.next before flipping curr.next = prev, or you lose the rest of the list.
- When curr falls off the end, prev is the new head.
- The recursive version is elegant but O(n) space (call stack); iterative is safer for long lists.
- Reversal is a sub-step in many harder problems: reverse a sublist, reverse in k-groups, palindrome check.