Merge k Sorted Lists LeetCode Solution

Here, We see Merge k Sorted Lists problem Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc., with different approaches.

 Merge k Sorted Lists LeetCode Solution

Merge k Sorted Lists LeetCode Solution

Problem Statement ->

You are given an array of k linked-lists lists, each linked list is sorted in ascending order. Merge all the linked lists into one sorted linked list and return it.

Example 1:
Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: The linked-lists are:
[
  1->4->5,
  1->3->4,
  2->6
]
merging them into one sorted list:
1->1->2->3->4->4->5->6

Example 2:
Input: lists = []
Output: []

Example 3:
Input: lists = [[]]
Output: []

Merge k Sorted Lists Leetcode Solution C++ ->

class Solution { public: ListNode* mergeKLists(vector<ListNode*>& lists) { priority_queue<ListNode*, vector<ListNode*>, compare> q; for (auto l : lists) { if (l) { q.push(l); } } ListNode pre(0); ListNode *node = &pre; while (q.size()) { ListNode *top = q.top(); q.pop(); node->next = top; node = node->next; if (top->next) { q.push(top->next); } } return pre.next; } struct compare { bool operator()(const ListNode* l1, const ListNode* l2) { return l1->val > l2->val; } }; };
Code language: C++ (cpp)

Merge k Sorted Lists Leetcode Solution Java ->

class Solution { public ListNode mergeKLists(ListNode[] lists) { return partion(lists,0,lists.length-1); } public static ListNode partion(ListNode[] lists,int s,int e){ if(s==e) return lists[s]; if(s<e){ int q=(s+e)/2; ListNode l1=partion(lists,s,q); ListNode l2=partion(lists,q+1,e); return merge(l1,l2); }else return null; } public static ListNode merge(ListNode l1,ListNode l2){ if(l1==null) return l2; if(l2==null) return l1; if(l1.val<l2.val){ l1.next=merge(l1.next,l2); return l1; }else{ l2.next=merge(l1,l2.next); return l2; } } }
Code language: Java (java)

Merge k Sorted Lists Leetcode Solution JavaScript ->

function mergeLists(a, b) { const dummy = new ListNode(0); let temp = dummy; while (a !== null && b !== null) { if (a.val < b.val) { temp.next = a; a = a.next; } else { temp.next = b; b = b.next; } temp = temp.next; } if (a !== null) { temp.next = a; } if (b !== null) { temp.next = b; } return dummy.next; } var mergeKLists = function(lists) { if (lists.length === 0 ) { return null; } while (lists.length > 1) { let a = lists.shift(); let b = lists.shift(); const h = mergeLists(a, b); lists.push(h); } return lists[0]; };
Code language: JavaScript (javascript)

Merge k Sorted Lists Leetcode Solution Python ->

class Solution(object): def mergeKLists(self, lists): if not lists: return None if len(lists) == 1: return lists[0] mid = len(lists) // 2 l, r = self.mergeKLists(lists[:mid]), self.mergeKLists(lists[mid:]) return self.merge(l, r) def merge(self, l, r): dummy = p = ListNode() while l and r: if l.val < r.val: p.next = l l = l.next else: p.next = r r = r.next p = p.next p.next = l or r return dummy.next def merge1(self, l, r): if not l or not r: return l or r if l.val< r.val: l.next = self.merge(l.next, r) return l r.next = self.merge(l, r.next) return r
Code language: Python (python)