Merge Two Sorted Linked Lists
Merge two sorted singly linked lists into one sorted linked list by iterating through both lists and comparing values. This classic problem is a fundamental building block for merge sort on linked lists and demonstrates the two-pointer technique. Can be solved iteratively in O(1) space or recursively with O(n+m) call stack space. Essential for understanding linked list manipulation.
Visualization
Interactive visualization for Merge Two Sorted Linked Lists
Interactive visualization with step-by-step execution
Implementation
1function mergeTwoLists(l1: ListNode | null, l2: ListNode | null): ListNode | null {
2 const dummy = new ListNode(0);
3 let current = dummy;
4
5 while (l1 && l2) {
6 if (l1.val <= l2.val) {
7 current.next = l1;
8 l1 = l1.next;
9 } else {
10 current.next = l2;
11 l2 = l2.next;
12 }
13 current = current.next;
14 }
15
16 current.next = l1 || l2;
17 return dummy.next;
18}
19
20// Recursive solution
21function mergeTwoListsRecursive(l1: ListNode | null, l2: ListNode | null): ListNode | null {
22 if (!l1) return l2;
23 if (!l2) return l1;
24
25 if (l1.val <= l2.val) {
26 l1.next = mergeTwoListsRecursive(l1.next, l2);
27 return l1;
28 } else {
29 l2.next = mergeTwoListsRecursive(l1, l2.next);
30 return l2;
31 }
32}Deep Dive
Theoretical Foundation
Merge Two Sorted Lists uses a two-pointer approach similar to the merge step in merge sort. Use a dummy node to simplify edge cases (empty lists). Compare the current nodes of both lists, attach the smaller one to the result, and advance that list's pointer. Continue until one list is exhausted, then append the remainder of the other list (already sorted). Iterative solution uses O(1) extra space. Recursive solution is elegant but uses O(n+m) stack space. Time: O(n+m) as each node is visited once.
Complexity
Time
O(n + m)
O(n + m)
O(n + m)
Space
O(1) iterative, O(n+m) recursive
Applications
Industry Use
Merge sort for linked lists
Database join operations
Merging sorted log files
Combining sorted streams
Priority queue merging
Sorted iterator combination
Use Cases
Related Algorithms
Binary Search Tree (BST)
A hierarchical data structure where each node has at most two children, maintaining the property that all values in the left subtree are less than the node's value, and all values in the right subtree are greater. This ordering property enables efficient O(log n) operations on average for search, insert, and delete. BSTs form the foundation for many advanced tree structures and are fundamental in computer science.
Stack
LIFO (Last-In-First-Out) data structure with O(1) push/pop operations. Stack is a fundamental linear data structure where elements are added and removed from the same end (top). It's essential for function calls, expression evaluation, backtracking algorithms, and undo operations in applications.
Queue
FIFO (First-In-First-Out) data structure with O(1) enqueue/dequeue operations. Queue is a fundamental linear data structure where elements are added at one end (rear) and removed from the other end (front). Essential for breadth-first search, task scheduling, and buffering systems.
Hash Table (Hash Map)
A data structure that implements an associative array abstract data type, mapping keys to values using a hash function. Hash tables provide O(1) average-case time complexity for insertions, deletions, and lookups, making them one of the most efficient data structures for key-value storage. The hash function computes an index into an array of buckets from which the desired value can be found.