clueless coding // TODO: be smarter

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.