LeetCode #21 Merge Two Sorted Lists

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.

Example:

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

Solution — Iteration

Use two pointers for tracking two lists. Compare l1 with l2 at first and decide small and large pointers. At each iteration, we will use a tail pointer to find the node whose value is larger than large in the list in which small is. And change small and large interactively.

Complexity

We will finally traverse each list only once in these two loops so time complexity will be O(m+n) if m and n denotes to amount of nodes of these two lists.

It’s trivial that it only uses O(1) extra space.

Solution — Recursion

Take out first node of the list which has smaller head node value, and recursively call self for rest two lists.

Complexity

It’s clear that at each function call it only takes O(1) time and extra space. And it may need O(m+n) times function calls for traversing all nodes in l1 and l2 if m and n denote to amount of nodes in two lists. Therefore, time and space complexity are both O(m+n).