Merge k sorted linked lists

Disseminating the "merge k sorted linked lists" problem from

Mon Mar 09 2020

A common question interview candidates are asked is to merge k sorted linked lists. This is available for practice on Leetcode.

k sorted linked lists = just some number of sorted linked lists

Problem description

Given k number of linked lists, create a new single linked list that is ordered. Analyze the time and space complexity.

A good solution for time complexity is O(N log k) where O is the number of operations N is the total number of items in the list and k is the number of linked lists. A good solution should also require no additional space/memory other than the memory already used e.g. constant O(1).

The algorithm

You want to merge the following 3 linked lists, list1, list2 and list3

2 -> 3 -> 4 -> 5
4 -> 5 -> 6 -> 7 -> 8

So that you have the following flattened final linked list

2 -> 3 -> 4 -> 4 -> 5 -> 5 -> 6 -> 7 -> 8 -> 20

As you construct the newly merged linked list you’ll be moving through the existing linked lists. Once an item has been added to the merged list there is no reason to return to this item. Therefore updating the head of the list as we construct a new merged list is an acceptable approach.

With each iteration, 1 item from the front of list1 or list2 or list3 will be plucked

list1 list2 list3 lowest_value
2 4 20 2
3 4 20 3
4 4 20 4 (from list1 )
5 4 20 4
5 5 20 5 (from list1 )
5 20 5
6 20 6
7 20 7
8 20 8
20 20


  1. Evaluate each head node of each input list to find the head with the lowest value
  2. Attach this head node to the tail of your flattened output list
  3. Make the head of the input list point the next node if one exists otherwise you’ve exhuasted this list. You just remove the node, so that you won’t see it again in the next iteration
  4. Repeat until there are no lists with nodes left

Python Code

This code passes all tests in LeetCode.


class ListNode:
    Basic data structure for a singly-linked list.

    def __init__(self, x):
        self.val = x = None

class Solution:
    Wrapper class for LeetCode solution

    def mergeKLists(self, lists: [ListNode]) -> ListNode:
        lists: list of ListNode
            Multiple linked lists, each can be traversed using the next property

            The head of a newly constructed ordered and flattened linked list

        if lists:
            lists = [l for l in lists if l]

        if not lists:
            return None

        # Setup the head of the new ordered merged linked list
        list_with_lowest_value = min(lists, key=lambda l: l.val)
        self._update_list_head(lists=lists, head_to_update=list_with_lowest_value)
        merged_list_head = list_with_lowest_value
        merged_list_cur = merged_list_head

        # Build new ordered merged linked list
        while lists:
            list_with_lowest_value = min(lists, key=lambda l: l.val)
   = list_with_lowest_value
            merged_list_cur =
            self._update_list_head(lists=lists, head_to_update=list_with_lowest_value)
        return merged_list_head

    def _update_list_head(cls, lists: [ListNode], head_to_update: ListNode):
        Updates the head reference of one list to the next item in that list

            index = lists.index(head_to_update)
            lists[index] =

Sample run code for experimentation and debugging

def main():
    """ The entry point of the python script """

    sln = Solution()

    # Test data 2 linked lists
    list1_item1 = ListNode(8)
    list1_item2 = ListNode(9)
    list1_item3 = ListNode(9) = list1_item2 = list1_item3

    list2_item1 = ListNode(3)

    # Print out the flattened linked list
    merged_list = sln.mergeKLists([list1_item1, list2_item1])
    while (merged_list and merged_list.val):
        merged_list =

if __name__ == "__main__":

Useful links

Paul Ness

Paul S. Ness Software engineer with ten years of experience in a variety of industries such travel, payments, medical, fine art and publishing.