Merge M Sorted Lists
Hard Problems DSA practice problem on Onlearn.
Difficulty: hard.
Topics: Efficiently merging M sorted lists, Merge Sort, Priority Queue, Divide and Conquer, Linked List, Heap/Priority Queue, Two Pointers, complexity analysis, priority queue, merging algorithms, sorting algorithms, divide and conquer, Merging K Sorted Arrays/Lists.
Merge k Sorted Lists You are given an array of k linked lists, where each linked list is sorted in ascending order. Merge all the linked lists into one sorted linked list and return it. Write a function: ListNode mergeKLists(vector<ListNode & lists) Input Specification: lists: An array of k singly linked lists (may contain empty lists) Each ListNode is defined as: struct ListNode { int val; ListNode next; ListNode() : val(0), next(nullptr) {} ListNode(int x) : val(x), next(nullptr) {} ListNode(int x, ListNode next) : val(x), next(next) {} }; The input may contain up to 10^4 linked lists Each linked list may contain up to 500 elements Element values range between 10^4 and 10^4 Output Specification: Return the head of the merged sorted linked list Example 1: Input: lists = [[1,4,5],[1,3,4],[2,6]] Output: [1,1,2,3,4,4,5,6] Explanation: The sorted linked lists are merged into one. Example 2: Input: lists = [] Output: [] Example 3: Input: lists = [[]] Output: [] Constraints: 0 <= k <= 10^4 0 <= each list length <= 500 10^4 <= val <= 10^4 Difficulty: Medium