Linked List Reverse
Reverses a singly linked list by re-pointing node references.
Merges two sorted linked lists into one sorted list.
Merging two sorted linked lists into a single sorted list is one of the most elegant and practically important operations in computer science. The algorithm takes two linked lists, each already sorted in non-decreasing order, and combines them into one unified sorted list by carefully comparing and relinking nodes. This operation is the linked list analog of the merge step in Merge Sort, and it serves as a foundational building block in numerous algorithms across sorting, database systems, and distributed computing.
The merge operation has deep historical roots. John von Neumann described Merge Sort in 1945, and the merge step was recognized early on as its most critical component. When applied to linked lists rather than arrays, the merge becomes particularly elegant because nodes can be relinked in place without allocating new memory. This in-place relinking property is one of the key advantages linked lists hold over arrays for merge-based algorithms.
tail pointer tracks the end of the merged list built so far.tail.next and advance that input list's pointer to its next node. Then advance tail to the newly appended node.tail.next. Since that remaining portion is already sorted, no further comparisons are needed.dummy.next, skipping the sentinel node.The dummy head technique deserves special attention. Without it, the code would need an if-else block to handle the first attachment separately from all subsequent ones, adding complexity and potential for bugs. By using a dummy node, every attachment follows the same code path, resulting in cleaner and more maintainable logic. This pattern appears throughout linked list programming and is worth internalizing.
| Metric | Value |
|---|---|
| Time | O(n + m) |
| Space | O(1) |
Where n and m are the lengths of the two input lists. Every node is visited exactly once during the comparison loop, and the merge is performed in place by re-pointing existing node references. No new nodes are created, and the only extra memory used is a constant number of pointer variables. The dummy node itself is a single allocation that does not depend on input size.
Merging two sorted arrays requires O(n + m) extra space for the output array because array elements cannot be rearranged in place the way linked list nodes can be relinked. This gives linked list merging a clear advantage in space efficiency. However, arrays benefit from cache locality and random access, so in practice the choice depends on the broader context of the application.
Merging sorted lists is a critical subroutine in several important algorithms and systems. In Merge Sort for linked lists, the list is recursively split in half, each half is sorted, and the two halves are merged using exactly this algorithm. For the k-way merge problem, where k sorted lists must be combined into one, a min-heap is used to efficiently select the smallest current element across all k lists, and the merge logic for attaching nodes follows the same pattern described here. Database engines use merge joins to combine two sorted relations on a join key, walking through both in lockstep with logic nearly identical to sorted list merging. In distributed systems, sorted run merging is used in external sort algorithms where data too large for memory is sorted in chunks and then merged from disk.
This algorithm should be your go-to approach whenever you need to combine two sorted sequences represented as linked lists. It is a classic interview problem that tests understanding of pointer management, sentinel nodes, and the two-pointer merging technique. The same conceptual approach generalizes naturally to merging sorted iterators, sorted file streams, and any pair of sorted sequences where elements can be consumed one at a time and compared efficiently.