Merge sorted linked lists

1. Problem statement

Merge two sorted linked lists together into a new linked list (Aziz et al., 2018, p. 92).

2. Insights

Because the input lists are already sorted, we only need to traverse through them once. We just have to make sure that we choose the node that has the smallest value in either list, and then proceed to the next node.

The other thing to keep in mind is that we want to append to the list by adding to a tail node. Otherwise if we keep appending from the head, we'll end up prepending things instead of appending things, ending up with nodes in reversed order.

Note that we use the linked list library implemented in "Linked lists". There, the insert() method creates a new LinkedList object each time. This is a bit expensive because we already have the objects allocated in the input lists a and b.

3. Solution(s)

3.1. Always append to the tail

Here's the code.

🔗
def merge(a: LinkedList, b: LinkedList) -> LinkedList:
    head = tail = LinkedList()
    a = a.next
    b = b.next
    while a or b:
        if a and b:
            if a.elt < b.elt:
                tail.next = a
                a = a.next
            else:
                tail.next = b
                b = b.next
        else:
            tail.next = a or b
            break
        tail = tail.next
    return head

Now let's go over this in detail.

First we create a new linked list node. We create two references to it, head and tail. We will modify tail by moving it along down the linked list we will build up when we traverse through the input lists. When we're done we will return the head node which we will leave untouched during this algorithm.

merge(1/7) 🔗
def merge(a: LinkedList, b: LinkedList) -> LinkedList:
    head = tail = LinkedList()

We assume that the input lists' head nodes do not contain any data themselves. And so we "shift" the head nodes of a and b by one node as a preparatory step.

merge(2/7) 🔗
    a = a.next
    b = b.next

Now comes the traversal. We traverse as long as either input list has nodes.

merge(3/7) 🔗
    while a or b:

Within each iteration, we check for 2 main cases:

  1. both a and b have nodes, or
  2. only one or both are at the tail (None type).

If both lists have nodes, we do the comparison check to determine which node has the smaller element. Then we make tail.next point to this node. We then advance the node we chose to its next one (because we must not check this node again in a future comparison).

merge(4/7) 🔗
        if a and b:
            if a.elt < b.elt:
                tail.next = a
                a = a.next
            else:
                tail.next = b
                b = b.next

If either or both input lists are empty, then we simply make tail.next point to the non-empty one. If both are empty then a or b evaluates to None, which is still what we want. Then we break out of the loop to save time because there is nothing more to compare.

merge(5/7) 🔗
        else:
            tail.next = a or b
            break

Finally before we end the iteration, we advance the tail node. This is important because we want to append to the list as we traverse along the input lists to find the next smallest element.

merge(6/7) 🔗
        tail = tail.next

When we're done we just need to return the original head node.

merge(7/7) 🔗
    return head

3.1.1. Complexity

  • Time: \(O(a+b)\) where \(a\) and \(b\) are the number of nodes in the input lists for the worst-case, where both input lists have similar numbers of nodes. In the best case, one list is much shorter than the other and we can break out of the loop early.
  • Space: \(O(1)\) because we only create 1 new node for the returned head node.

4. Tests

🔗
from hypothesis import given, strategies as st
import random
import unittest

from linked_list.linked_list import LinkedList

merge

class Test(unittest.TestCase):
    def test_merge_simple_cases(self):
        cases = [
            ([], [], []),
            ([1], [], [1]),
            ([], [1], [1]),
            ([1], [1], [1, 1]),
            ([1, 2, 3], [1], [1, 1, 2, 3]),
            ([1, 2], [1, 3], [1, 1, 2, 3]),
            ([1, 3, 5], [2, 4, 6, 8, 10], [1, 2, 3, 4, 5, 6, 8, 10]),
            ([1, 2, 3], [], [1, 2, 3]),
            ([], [1, 2, 3], [1, 2, 3]),
        ]
        for list_a, list_b, list_expected in cases:
            a = LinkedList(*list_a)
            b = LinkedList(*list_b)
            expected = LinkedList(*list_expected)

            got = merge(a, b)
            self.assertEqual(got, expected,
                            msg=f'{got=} {list_expected=}')

    @given(st.lists(st.integers(min_value=1, max_value=100),
                    min_size=0,
                    max_size=20))
    def test_merge_random(self, given_elts: list[int]):
        size_a = random.randint(0, len(given_elts))
        a = given_elts[0:size_a]
        b = given_elts[size_a:]
        expected = LinkedList(*sorted(given_elts))
        got = merge(LinkedList(*sorted(a)),
                    LinkedList(*sorted(b)))
        self.assertEqual(got, expected,
                        msg=f'{got=} {expected=}')
if __name__ == "__main__":
    unittest.main(exit=False)

5. References

Aziz, A., Lee, T.-H., & Prakash, A. (2018). Elements of Programming Interviews in Python: The Insiders’ Guide. CreateSpace Independent Publishing Platform (25 July. 2018).