Merge Two Sorted Linked Lists

Feb 6, 2020 by Chris Luedtke

Description

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

Solution

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 ListNodes:

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 O(n) time.

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