# 21. Merge Two Sorted Lists

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:

• 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.

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 + merge(list1[1:], list2), when list1 < list2.
• list2 + merge(list1, list2[1:]), otherwise.

Note: Notice how to handle the corner cases.

Improvement:

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

Comment Junhao Wang
a software engineering cat