Back to Study Material Data Structures and Algorithms

Reverse Linked List

Reversing a linked list means changing the direction of all next pointers so that the last node becomes the first and the first becomes the last. This is o...

Reverse Linked List

Flipping the Direction of a Linked List Iteratively and Recursively

Reversing a linked list means changing the direction of all next pointers so that the last node becomes the first and the first becomes the last. This is one of the most common linked list problems in technical interviews and tests your ability to manage multiple pointers simultaneously without losing track of nodes.

The iterative approach uses three pointers: prev, current, and next_node. Initialize prev to null and current to head. In each iteration: save current.next in next_node so you do not lose the rest of the list, reverse the pointer by setting current.next to prev, advance prev to current, and advance current to next_node. When current becomes null, prev points to the new head. Update head to prev. The loop runs n times, giving O(n) time and O(1) space.

A common mistake is forgetting to save current.next before overwriting current.next. Without this save, you lose the rest of the list permanently. Always save next_node as the very first line of the loop body.

The recursive approach is more elegant but uses O(n) stack space. The base case: if head is null or head.next is null, return head (the new head of the reversed list). Recursive step: reverse the rest of the list from head.next onward, getting new_head as the return value. Then make head.next.next point back to head (reversing the last link processed), and set head.next to null (it now becomes the tail). Return new_head.

For doubly linked lists, reversing also requires swapping each node's prev and next pointers. For each node, swap node.next and node.prev, advance to the original next (now stored in node.prev after the swap), and update head to the last node processed.

Partial reversal, reversing only a sublist from position left to right, is a useful variant. Find the node just before position left, then reverse exactly (right minus left plus one) nodes using the same three-pointer technique, and reconnect the reversed portion to the nodes before and after it.

Worked example: reverse the list [1, 2, 3, 4, 5]. Starting state: prev equals null, current equals node(1). Iteration 1: save next(2), set 1.next to null, prev to node(1), current to node(2). Iteration 2: save next(3), set 2.next to node(1), prev to node(2), current to node(3). Continue through 5. After the loop: prev points to node(5), which is the new head. Result: [5, 4, 3, 2, 1].

Interview tip: practice reversing a linked list until you can write the iterative three-pointer version from memory in under two minutes. It appears in a surprisingly large fraction of linked list interview questions, either directly or as a subroutine.