Reference: LeetCode EPI 7.1
Difficulty: Easy

Problem

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists (non-destructive).

Example: 

1
2
Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4

Follow up:

  • Space from $O(n + m)$ to $O(1)$.
  • Solve the same problem when the lists are doubly linked. Marked
    • Set previous node during the process.

Analysis

Naive Solution

Append the two lists together and sort the resulting list. But it does not use the fact that the two initial lists are sorted.

Time: $O((n + m)\log{(n + m)})$ (use witch sorting algorithm?)

Iteration

Note: When n1 or n2 becomes null, it is not necessary to walk through the rest nodes of the list.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public ListNode iteration(ListNode n1, ListNode n2) {
  ListNode dummy = new ListNode(-1);
  ListNode prev = dummy;

  while (n1 != null && n2 != null) {
    if (n1.val <= n2.val) {
      prev.next = n1;
      n1 = n1.next;
    } else {
      prev.next = n2;
      n2 = n2.next;
    }
    prev = prev.next;  // don't forget
  }

  prev.next = (n1 != null) ? n1 : n2;
  return dummy.next;
}

Time: $O(n + m)$, since each time exactly one of n1 or n2 will move by one step. The best case occurs when one list is much shorter than the other and the values are less than the ones in the other list.
Space: $O(1)$ because of pointers.

Recursion

We can define the result of a merge operation on two lists as follows:

  • list1[0] + merge(list1[1:], list2), when list1[0] < list2[0].
  • list2[0] + merge(list1, list2[1:]), otherwise.
1
2
3
4
5
6
// Example
list1 = [1 2 4]
list2 = [3 5 7]
// Start:
1 + merge([2 4], [3 5 7])
2 + merge([4], [3 5 7])

Note: Notice how to handle the corner cases.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public ListNode recursion(ListNode n1, ListNode n2) {
  return mergeHelper(n1, n2);
}

// n1 == null, n2 != null => n2
// n1 != null, n2 == null => n1
// n1 == null, n2 == null => null
private ListNode merge(ListNode n1, ListNode n2) {
  if (n1 == null || n2 == null) { // this line is redundant
    if (n1 == null) return n2;
    if (n2 == null) return n1;
  }
  if (n1.val < n2.val) {
    n1.next = merge(n1.next, n2);
    return n1;
  } else {
    n2.next = merge(n2.next, n1);
    return n2;
  }
}

Improvement:

1
2
3
4
5
6
7
8
9
10
11
12
13
private ListNode merge(ListNode n1, ListNode n2) {
  if (n1 == null) return n2;
  if (n2 == null) return n1;
  
  // n1, n2 NotNull
  if (n1.val < n2.val) {
    n1.next = merge(n1.next, n2);
    return n1;
  } else {
    n2.next = merge(n1, n2.next);
    return n2;
  }
}

Time: $O(n + m)$, number of elements in two lists.
Space: $O(n + m)$, $n + m$ stack frames in total.