Merge two sorted linked lists

What is a Linked List?

A linked list is a data structure in which each element points to the following one. Here, we have a class Node with a value and a link to the next element. We can also have double linked lists where each element points to the next and previous element.

The relevant bit of (collapsed) code they use to define the linked list is:

class SinglyLinkedListNode:
    def __init__(self, node_data):
        self.data = node_data
        self.next = None

Using this, we can build a recursive solution.

sys.setrecursionlimit(10000)

def mergeLists(head1, head2):
    if head1 is None:
        return head2
    if head2 is None:
        return head1
    if head1.data <= head2.data:
        head1.next = mergeLists(head1.next, head2)
        return head1
    head2.next = mergeLists(head1, head2.next)
    return head2

Trust in recursivity (always)

When we make a recursive algorithm, we need to think about two things.

The initial steps that define the basis element (One element or an empty list).

And the “in progress” steps. We select whichever list has the smaller element in the first position. Then we know that the merged list consists of that element followed by the result of the merge between the rest of that list (after the selected element) and the other list.

Be careful, recursive solution can require a lot of memory. Also, Python has a recursion limit. You can change it using sys.setrecursionlimit. In this challenge, adding sys.setrecursionlimit(10000) should allow the reference solution code to pass all of the test cases.

We can also implement this non-recursively by building up a new list - the recursive solution here is in place, so it alters our original lists. We’ll aslo take advantage of the SingleLinkedList class that they have provided us. It’s not necessary, but is very convenient.

def mergeLists(head1, head2):
    newlist = SinglyLinkedList()

    while head1 and head2:
        if head1.data <= head2.data:
            newlist.insert_node(head1.data)
            head1 = head1.next
        else:
            newlist.insert_node(head2.data)
            head2 = head2.next

    # One of the lists ran out, empty out the other
    # The one that's empty will do nothing here
    while head1:
        newlist.insert_node(head1.data)
        head1 = head1.next

    while head2:
        newlist.insert_node(head2.data)
        head2 = head2.next

    return newlist.head