# LeetCode 21. Merge Two Sorted (Linked) Lists: Explanation and C++ Solution

## Problem Statement

Merge two sorted (ascending order) children linked lists and return it as a new, sorted (ascending order) list. The new list should be made by splicing together the nodes of the first two lists.

```
Function Signature:
C++
struct Node {
Node(int val) : value(val), next(NULL) {}
int value;
Node* next;
}
Node* mergeLists(Node* first, Node* second) {...}
Inputs:
first = 3 -> 5 -> 7 -> 9 -> NULL
second = 2 -> 4 -> 6 -> 8 -> NULL
Outputs:
out = 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> NULL
Inputs:
first = 3 ->
second = -> NULL
Outputs:
out = 3 -> NULL
```

## Solution #1 (optimal): Simultaneous Traversal

O(N) runtime, O(1) memory

This problem can seem a lot more complicated that it really is, especially if you start approaching it by trying to splice the two lists together in their entirety. Instead of thinking about that, we should frame it in a different way. We’ll tackle the problem by constructing the final, sorted list one element at a time.

The first question we need to ask is this: what makes a sorted list? A sorted list has its smallest element at the head, and its largest element at its tail. If our goal is to construct the final list one element at a time, we should start at the head. That leads easily into the idea that the very first element - the head of the new list - is the minimum element in either the first or the second list.

How do we find that element? There’s a key characteristic defined for us in the problem spec - the children lists are **sorted**. We can utilize this fact - the smallest
element in the first list is at its head. The smallest element in the second list is at its head. We’re looking for the minimum element in either list, so we can simply
compare the head elements of each list and find the minimum.

(Hint: read your problem specs carefully! If a spec says that some data is sorted, alarms should immediately go off. A sorted set of data can offer huge benefits when trying to implement efficient algorithms.)

For example:

```
Inputs:
first = 3 -> 5 -> 7 -> 9 -> NULL
second = 2 -> 4 -> 6 -> 8 -> NULL
```

For the first element of our merged list, we know that we only need to look at 2 and 3 - they’re the only candidates that could be the smallest element in either list.

So, how do we find our second element? Again, we’re looking for the smallest element in either list, **DISREGARDING THE MINIMUM WE JUST FOUND**. We can follow the same process
as before - we simply don’t consider the element we’ve already used.

To illustrate the process in whole:

```
First
first = 3 -> 5 -> 7 -> 9 -> NULL
second = 2 -> 4 -> 6 -> 8 -> NULL
compare 2 and 3, 2 < 3
output = 2 -> NULL
Second
first = 3 -> 5 -> 7 -> 9 -> NULL
second = 4 -> 6 -> 8 -> NULL
compare 3 and 4, 3 < 4
output = 2 -> 3 -> NULL
Third
first = 5 -> 7 -> 9 -> NULL
second = 4 -> 6 -> 8 -> NULL
compare 5 and 4, 4 < 5
output = 2 -> 3 -> 4 -> NULL
...
```

If we continue that process until the very last element, we’ll create a spliced, sorted list from two parts! But there’s one more thing to consider - what happens when one list runs out of elements, and we’re comparing NULL to a value?

```
Inputs:
First
first = 1 -> NULL
second = 2 -> 3 -> NULL
compare 1 and 2, 1 < 2
output = 1 -> NULL
Second
first = -> NULL
second = 2 -> 3 -> NULL
compare 2 and NULL?
```

In this case, we can simply append the list with remaining members to to the end of our final list. Why?

- We know that the list is sorted already
- We know that its head element is larger than the last element we inserted to our final list, i.e. the tail of the last list.

Therefore, simply appending the leftover list still creates a sorted list. If you don’t believe me, try it on the example above!

The code for this algorithm is pretty simple - while both lists have elements, we simply compare the heads of each and insert the smaller at the tail of our result. When one list runs out of elements, we just have to append the list with leftover elements to the end.

Note: In our implementation, we’ll set a ‘dummy’ node at the head of our combined list, to facilitate easy insertions.

```
Node* mergeLists(Node* first, Node* second) {
// dummy node
Node* head = new Node(-1);
Node* headRunner = head;
while (firstRunner && secondRunner) {
// find minimum between heads, and insert at tail
if (first.value < second.value) {
headRunner->next = first;
}
else {
headRunner->next = second;
}
// keep headRunner at the tail for easy insertions
headRunner = headRunner->next;
}
// one (or both) lists are out of elements here - append
if (first) {
headRunner->next = first;
}
else {
headRunner->next = second;
}
// remember to skip over the dummy node
return head->next;
}
```

If you prefer some less verbose code:

```
Node* mergeLists(Node* first, Node* second) {
Node* head = new Node(-1);
Node* headRunner = head;
while (firstRunner && secondRunner) {
headRunner->next = firstRunner.value < secondRunner.value ? firstRunner : secondRunner;
headRunner = headRunner->next;
}
headRunner->next = first ? first : second;
return head->next;
}
```

O(N) runtime - we only operate on each element once, regardless of the list they’re in.

O(1) memory - we’re only operating on the given lists, not storing anything.