Merge Two Sorted Linked Lists
Merge two sorted linked lists and return the first node of the merged list. The new list should be made by splicing together the nodes of the first two lists (don’t define any new data structures like python dictionaries or python lists).
# Definition for singly-linked list node class ListNode(object): def __init__(self, x): self.val = x self.next = None # Function Inputs # * first node of list 1 # * first node of list 2
In order to tackle this problem, we need a basic understanding of singly linked lists. A (singly) linked list is composed of nodes that are connected in a single direction.
Linked lists are very simple data structures. We can’t use python list features like index slicing (
list[0:4]) to access the values of our list. To know all the values of a linked list, we have to start at the very first node and read forward. Check out Dan Bader’s article for a more thorough explanation.
The barebones linked list implementation was provided:
class ListNode(object): def __init__(self, x): self.val = x self.next = None
We can make our own linked list composed of
my_list = ListNode(x=1) my_list.next = ListNode(x=3) my_list.next.next = ListNode(x=7)
We can walk through each node and print its value:
node = my_list while node: print(node.val) node = node.next >>> 1 3 7
And now we can approach our solution. This algorithm runs in
def merge_two_lists(l1: ListNode, l2: ListNode) -> ListNode: # create a blank node to start our merged list. We will add nodes to this list # in increasing order. merged_list_node_1 = ListNode(None) # make a "head" that will point to the blank node_1 to start. We'll move it # forward so it's always pointing to the last value of our merged list. head = merged_list_node_1 while l1 and l2: if l1.val <= l2.val: # add the smaller node to our merged list head.next = l1 # update l1 to refer to the next item of its list l1 = l1.next elif l2.val < l1.val: head.next = l2 l2 = l2.next # move our head pointer forward head = head.next # finally we need to add the last node from whichever list # was not empty when we broke out of the while loop above if l1: head.next = l1 elif l2: head.next = l2 # since the first item of our list is None, we return the next value return merged_list_node_1.next