Merge K Sorted Linked Lists | Dataford Interview Questions

Merge K Sorted Linked Lists

Medium

CodingLinked ListsSortingHeap

Asked 1w ago|

Google

Asked 7 times

Problem

At Meta, imagine multiple pre-sorted event streams need to be combined into one ordered feed. Given k sorted singly linked lists, merge them into one sorted linked list and return its head.

Formal Specification

Implement a function that takes lists, where lists[i] is the head of a sorted singly linked list or null. Each node contains an integer value and a next pointer. Return the head of a new merged sorted linked list formed by reusing the existing nodes.

Constraints

0 <= k <= 10^4
0 <= total number of nodes <= 10^5
-10^4 <= Node.val <= 10^4
Each linked list is sorted in non-decreasing order

Function Signature

def merge_k_lists(lists):

You are practicing as a guest. Sign up free to run your code against the sample data. Your draft stays right here.

def solve(rows):
    counts = {}
    for row in rows:
        ...
    return result

Next questions

Merge K Sorted Feed ListsMedium

Merge K Sorted ListsMedium

Merge K Sorted Lists OptimizationHard

Python 3.10