Merge Two Sorted Lists

Easylinked-listrecursion
Category: Linked List
Companies that ask this question:
AmazonMicrosoftFacebookGoogle
LeetCode →NeetCode →

Approach

Merge Two Sorted Lists

Problem Statement

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

Approach 1: Iterative

The iterative approach uses a dummy node to build the merged list step by step.

Algorithm

  1. Create Dummy Node: Start with a dummy node to simplify edge cases
  2. Compare and Link:
    • Compare values of current nodes from both lists
    • Link the smaller node to the result
    • Move forward in that list
  3. Append Remaining: When one list is exhausted, append the other
  4. Return: Return dummy.next (skip the dummy)

Time Complexity

  • Time: O(n + m) where n and m are the lengths of the two lists
    • We visit each node exactly once
  • Space: O(1) - only uses a few pointers

Visual Example

list1: 1 → 2 → 4
list2: 1 → 3 → 4

Step 1: Compare 1 and 1 → pick list1
Result: D → 1

Step 2: Compare 2 and 1 → pick list2  
Result: D → 1 → 1

Step 3: Compare 2 and 3 → pick list1
Result: D → 1 → 1 → 2

Step 4: Compare 4 and 3 → pick list2
Result: D → 1 → 1 → 2 → 3

Step 5: Compare 4 and 4 → pick list1
Result: D → 1 → 1 → 2 → 3 → 4

Step 6: Append remaining (4 from list2)
Result: D → 1 → 1 → 2 → 3 → 4 → 4

Approach 2: Recursive

A more elegant solution using recursion.

Algorithm

  1. Base Cases:
    • If list1 is empty, return list2
    • If list2 is empty, return list1
  2. Recursive Case:
    • If list1.val < list2.val:
      • list1.next = merge(list1.next, list2)
      • return list1
    • Else:
      • list2.next = merge(list1, list2.next)
      • return list2

Time Complexity

  • Time: O(n + m)
  • Space: O(n + m) for recursion stack

Key Insights

  1. The dummy node trick simplifies handling the head
  2. No need to create new nodes - just rearrange pointers
  3. Remember to handle remaining nodes after one list is exhausted
  4. The lists maintain their sorted property during merge
  5. Recursive solution is elegant but uses stack space

Solution

java
1/**
2 * Merge Two Sorted Lists
3 *
4 * Time Complexity: O(n + m)
5 * Space Complexity: O(1) for iterative, O(n + m) for recursive
6 */
7
8class ListNode {
9    int val;
10    ListNode next;
11    ListNode() {}
12    ListNode(int val) { this.val = val; }
13    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
14}
15
16// Iterative Approach
17class Solution {
18    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
19        // Create dummy node to simplify edge cases
20        ListNode dummy = new ListNode(0);
21        ListNode current = dummy;
22        
23        // Compare and link nodes
24        while (list1 != null && list2 != null) {
25            if (list1.val < list2.val) {
26                current.next = list1;
27                list1 = list1.next;
28            } else {
29                current.next = list2;
30                list2 = list2.next;
31            }
32            current = current.next;
33        }
34        
35        // Append remaining nodes
36        current.next = list1 != null ? list1 : list2;
37        
38        return dummy.next;
39    }
40}
41
42// Recursive Approach
43class Solution2 {
44    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
45        // Base cases
46        if (list1 == null) return list2;
47        if (list2 == null) return list1;
48        
49        // Recursive case
50        if (list1.val < list2.val) {
51            list1.next = mergeTwoLists(list1.next, list2);
52            return list1;
53        } else {
54            list2.next = mergeTwoLists(list1, list2.next);
55            return list2;
56        }
57    }
58}
59
Loading visualizer...