# 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:**

1 | Input: 1->2->4, 1->3->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 | public ListNode iteration(ListNode n1, ListNode n2) { |

**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 | // Example |

**Note:** Notice how to handle the corner cases.

1 | public ListNode recursion(ListNode n1, ListNode n2) { |

**Improvement:**

1 | private ListNode merge(ListNode n1, ListNode n2) { |

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