# 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 `ListNode`s:

``````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.

while l1 and l2:
if l1.val <= l2.val:
# add the smaller node to our merged list
# update l1 to refer to the next item of its list
l1 = l1.next

elif l2.val < l1.val:
l2 = l2.next

# move our head pointer forward