Reverse Linked List
The drill: Turn a singly linked list around so every arrow points the other way, and hand back what used to be the tail.
A singly linked list arrives, and the job is to flip its direction entirely — every node that used to point forward now points backward, and the node that used to be the tail becomes the new head.
The values inside the nodes never change; only the wiring between them does, and the list can be empty or hold just one node, in which case there's effectively nothing to flip.
The list comes back headed by what used to be its last node, with every arrow reversed all the way through.
- list length ranges from zero nodes up to a few thousand
- node values can be any integer, negative or positive
- only the pointer direction changes, never the stored values
- an empty list or single node reverses to itself
HINT 1 THE NUDGE
An array copy makes this trivial — and misses the point. The pointer version asks you to never lose your grip on the rest of the list.
HINT 2 THE STRUCTURE
At each node you need three handles at once: what is behind you (already reversed), where you stand, and what is ahead (untouched).
HINT 3 ONE STEP FROM THE ANSWER
Walk once: save next, point current back at prev, then shuffle prev and current forward. When current runs off the end, prev is the new head.
List is 1 → 2 → 3 → 4 → 5. prev starts null, curr sits at node 1 — reverse the arrows one at a time.
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
prev = None
curr = head
while curr:
nxt = curr.next
curr.next = prev
prev = curr
curr = nxt
return prevclass Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
vals = []
node = head
while node:
vals.append(node.val)
node = node.next
rebuilt = None
for v in vals:
rebuilt = ListNode(v, rebuilt)
return rebuiltclass Solution {
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode nxt = curr.next;
curr.next = prev;
prev = curr;
curr = nxt;
}
return prev;
}
}class Solution {
public ListNode reverseList(ListNode head) {
List<Integer> vals = new ArrayList<>();
for (ListNode n = head; n != null; n = n.next) {
vals.add(n.val);
}
ListNode rebuilt = null;
for (int v : vals) {
rebuilt = new ListNode(v, rebuilt);
}
return rebuilt;
}
}✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED