Coder's Cat

2019-12-24

## Leetcode Problem

https://leetcode.com/problems/merge-two-sorted-lists/

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.

Example:

## Explanation

The logic is simple, iterate both link list nodes, compare the value of nodes and add the next to result.

Use dummy node for simplifying the code, and another corner case is if a link list is longer than the other one.

Assume the length of two link list is M and N, the time complexity is $O(Max(M, N))$.

### Recursive version

Another solution is using recursive iteration, the corner case is handled by the first two if test.

Preparing for an interview? Check out this!