Merge Sorted Lists
Merges two sorted linked lists into one sorted list.
Reverses a singly linked list by re-pointing node references.
Reversing a linked list is one of the most fundamental operations in computer science and a cornerstone interview question that tests a programmer's understanding of pointer manipulation. The operation changes the direction of all pointers in a singly linked list so that the last node becomes the new head and the original head becomes the tail, with every internal pointer flipped to point backward. Despite its apparent simplicity, linked list reversal is a surprisingly rich topic that connects to important ideas in data structure design, algorithm composition, and systems programming.
The concept of linked lists dates back to the 1950s and 1960s, when Allen Newell, Cliff Shaw, and Herbert A. Simon developed them for their Information Processing Language at RAND Corporation. Reversal of linked structures became one of the earliest studied pointer-based operations, and it remains a staple of computer science education because it cleanly illustrates the challenge of modifying a data structure in place without losing references.
The iterative approach uses three pointers to walk through the list and reverse each link in a single pass.
prev = null, curr = head, and next = null. The prev pointer will track the already-reversed portion of the list, while curr points to the node currently being processed.curr.next in next. This is critical because once we reverse the current node's pointer, we would otherwise lose our reference to the rest of the list.curr.next = prev, which flips the current node's pointer from pointing forward to pointing backward toward the already-reversed portion.prev = curr and curr = next, sliding our window one node forward through the list.curr is null, meaning we have processed every node. At this point, prev points to what was formerly the last node, which is now the new head of the reversed list.There is also a recursive approach where the function calls itself on the rest of the list and then fixes up the pointers on the way back. While elegant, the recursive version uses O(n) call stack space, making it less suitable for very long lists where stack overflow is a concern.
| Metric | Value |
|---|---|
| Time | O(n) |
| Space | O(1) iterative, O(n) recursive |
The iterative approach visits each node exactly once and uses only a constant number of pointer variables regardless of list length. The recursive approach has the same O(n) time complexity but requires O(n) space for the call stack, one frame per node.
Reversing an array in place is straightforward using two pointers that swap elements from opposite ends, moving inward. Linked list reversal is fundamentally different because nodes are not stored contiguously in memory and we cannot index into the middle of the list. Instead, we must traverse sequentially and re-point each node's next reference. This distinction makes linked list reversal a much more instructive exercise in understanding how reference-based data structures work compared to index-based ones.
Beginners frequently make the mistake of modifying curr.next before saving the next pointer, which severs the connection to the rest of the list and causes data loss. Another common error is forgetting to update the head of the list to point to prev after the loop completes. These mistakes highlight why the three-pointer technique is taught so deliberately: each step must happen in the correct order.
Linked list reversal appears far beyond interview whiteboards. In practice, it is used in undo stacks where operations must be replayed in reverse order, in polynomial arithmetic where terms need to be reordered, and as a subroutine in algorithms that rotate a linked list by k positions. It is a building block for checking whether a linked list is a palindrome, where you reverse the second half and compare it node by node with the first half. It also appears in the classic problem of reversing nodes in k-groups, where segments of the list are reversed individually and then reconnected. Understanding this operation thoroughly opens the door to a wide family of linked list manipulation techniques.