##### Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/23.html

# 23 - Merge k Sorted Lists

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Example:

Input: [ 1->4->5, 1->3->4, 2->6 ]

Output: 1->1->2->3->4->4->5->6

### MergeSort solution

The first thing that comes to mind is the two-by-two merger, that is, the first two are merged first, and then the third is merged, and then the fourth to the kth. This kind of thinking is correct, but it is not efficient and cannot pass OJ, so we can only change the way of thinking. Divide and Conquer Approach are needed here.

Simply, it is divided into half and half, for example, k linked lists are first divided into the task of merging two k/2 linked lists, and then continuously divided down, until they are divided into tasks with only one or two linked lists, and start to merge.

For example, if you merge 6 linked lists, then according to the divide and conquer method, first merge 0 and 3, 1 and 4, and 2 and 5 respectively. So next time you only need to merge 3 linked lists, then merge 1 and 3, and finally merge with 2.

The k in the code is calculated by (n+1)/2, why add 1 here?

• This is for when n is odd, k can always start from the second half,
• for example, when n=5, then at this time k=3, then 0 and 3 are merged, 1 and 4 are merged, and the middle 2 is vacant.
• When n is an even number, adding 1 will not have any effect. For example, when n=4 and k=2, then 0 and 2 are combined, and 1 and 3 are combined, which perfectly solves the problem.
##### big-o analysis

time-complex O(N*logK)

• N is the total number of nodes
• k is the number of linked lists.

      public ListNode merge(ListNode[] lists, int start, int end) {

int mid = (end - start) / 2 + start;
ListNode leftHalf = merge(lists, start, mid);
ListNode rightHalf = merge(lists, mid + 1, end); • We can merge two sorted linked list in O(n) time where n is the total number of nodes in two lists.
• Sum up the merge process and we can get: sum all nodes logk times (height of tree) => O(Nlogk)

### Heap solution

Put the smallest node of each list into a priority queue (min heap). Every time a node is removed from the queue, the node is inserted into the next node in its list, And so on until all nodes have passed the priority queue.

Since the size of the priority queue is always k, and the complexity of each insertion is log k, a total of nk nodes have been inserted.

Heap solution: heap.offer(polled.next); Here, the offer() parameter of heap cannot be null, because polled is not null before updating currentNode

            if (polled.next != null) {
heap.offer(polled.next); // @note: offer()参数不能是null
}


The time complexity is O(n * k * logk), and the space complexity is O(k).

• public class Merge_k_Sorted_Lists {

public static void main(String[] args) {

Merge_k_Sorted_Lists out = new Merge_k_Sorted_Lists();
Solution s = out.new Solution();

ListNode l1 = null;
ListNode l2 = new ListNode(1);

s.mergeKLists(new ListNode[]{l1, l2});

}

public class Solution {
public ListNode mergeKLists(ListNode[] lists) {

if (lists == null || lists.length == 0) {
return null;
}

// same as merge sort array
return merge(lists, 0, lists.length - 1);
}

public ListNode merge(ListNode[] lists, int start, int end) {

// single list
if (start == end) {
return lists[start];
}

int mid = (end - start) / 2 + start;
ListNode leftHalf = merge(lists, start, mid);
ListNode rightHalf = merge(lists, mid + 1, end);

return mergeTwoLists(leftHalf, rightHalf);
}

// from previous question: 21 Merge Two Sorted Lists
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {

ListNode dummy = new ListNode(0);
ListNode current = dummy;

while (l1 != null || l2 != null) {
int v1 = (l1 == null ? Integer.MAX_VALUE : l1.val);
int v2 = (l2 == null ? Integer.MAX_VALUE : l2.val);

if (v1 < v2) {
current.next = l1;
l1 = l1.next;
} else {
current.next = l2;
l2 = l2.next;
}

current = current.next; // now current is the new end node, but still pointing to next node
current.next = null; // @note: key, cut this node from l1 or l2
}

return dummy.next;
}
}

}

#############

class Solution_Heap {
public ListNode mergeKLists(ListNode[] lists) {

if (lists == null || lists.length == 0) {
return null;
}

ListNode dummy = new ListNode(0);
ListNode current = dummy;

// put 1st of each list to heap
PriorityQueue<ListNode> heap = new PriorityQueue<>(
(a,b) -> a.val - b.val
);

//
Arrays.stream(lists).filter(Objects::nonNull).forEach(heap::offer);

while (heap.size() != 0) {
ListNode polled = heap.poll();

current.next = polled;
current = current.next;

if (polled.next != null) {
heap.offer(polled.next); // @note: heap.offer()参数不能是null
}
}

return dummy.next;
}
}

############

/**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode() {}
*     ListNode(int val) { this.val = val; }
*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
int n = lists.length;
if (n == 0) {
return null;
}
for (int i = 0; i < n - 1; ++i) {
lists[i + 1] = mergeLists(lists[i], lists[i + 1]);
}
return lists[n - 1];
}

private ListNode mergeLists(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode();
ListNode cur = dummy;
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) {
cur.next = l1;
l1 = l1.next;
} else {
cur.next = l2;
l2 = l2.next;
}
cur = cur.next;
}
cur.next = l1 == null ? l2 : l1;
return dummy.next;
}
}

• // OJ: https://leetcode.com/problems/merge-k-sorted-lists/
// Time: O(NlogK)
// Space: O(K)
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
ListNode dummy, *tail = &dummy;
auto cmp = [](auto a, auto b) { return a->val > b->val; };
priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> q(cmp);
for (auto list : lists) {
if (list) q.push(list); // avoid pushing NULL list.
}
while (q.size()) {
auto node = q.top();
q.pop();
if (node->next) q.push(node->next);
tail->next = node;
tail = node;
}
return dummy.next;
}
};

• # Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

import heapq

'''
__lt__(self, other) for <
__le__(self,other) for <=
__gt__(self, other) for >
__ge__(self, other) for >=
'''
# overwrite the comparison function, so the node can be comparable
# or else, error, TypeError: '<' not supported between instances of 'ListNode' and 'ListNode'
ListNode.__lt__ = lambda x, y: (x.val < y.val)

# define 'gt' will also work, so either lt or gt will do the compare job for ListNode
# ListNode.__gt__ = lambda x, y: (x.val > y.val)

class Solution:

def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
dummy = current = ListNode()
heap = []
for i, node in enumerate(lists):
if node:
# need to override
# or else error: TypeError: '<' not supported between instances of 'ListNode' and 'ListNode'
heapq.heappush(heap, node)

while heap:
anode = heapq.heappop(heap)

current.next = anode
current = current.next

if anode.next:
heapq.heappush(heap, anode.next)

return dummy.next

'''
tried to use node.val to order heap, but still got error TypeError: '<' not supported between instances of 'ListNode' and 'ListNode':

heapq.heappush(heap, (node.val, node))

'''

# based on merge 2 lists
# note for empty input
class Solution:
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
if lists is None or len(lists) == 0:
return None
return self.mergeKListsHelper(lists, 0, len(lists) - 1)

def mergeKListsHelper(self, lists: List[Optional[ListNode]], start: int, end: int) -> Optional[ListNode]:

if start == end:
return lists[start]

mid = int((start + end) / 2)

left = self.mergeKListsHelper(lists, start, mid)
# print(left)

right = self.mergeKListsHelper(lists, mid + 1, end)
# print(right)

return self.mergeTwoLists(left, right)

def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
dummy = ListNode()
current = dummy
# print("merging: ", list1)
# print("merging: ", list2)
while list1 or list2:
v1 = list1.val if list1 else float('inf')
v2 = list2.val if list2 else float('inf')

if v1 < v2:
current.next = list1
list1 = list1.next
else:
current.next = list2
list2 = list2.next
current = current.next

# print("merging result: ", dummy.next)

return dummy.next

############

# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
n = len(lists)
if n == 0:
return None
for i in range(n - 1): # this is o(N) times of merge, while if use divide-mid-mere then it's o(logN) times of merge
lists[i + 1] = self.mergeTwoLists(lists[i], lists[i + 1])
return lists[-1]

def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
dummy = ListNode()
cur = dummy
while l1 and l2:
if l1.val <= l2.val:
cur.next = l1
l1 = l1.next
else:
cur.next = l2
l2 = l2.next
cur = cur.next
cur.next = l1 or l2
return dummy.next

if __name__ == '__main__':

l1 = ListNode(1)
l1.next = ListNode(4)
l1.next.next = ListNode(5)

l2 = ListNode(1)
l2.next = ListNode(3)
l2.next.next = ListNode(4)

l3 = ListNode(2)
l3.next = ListNode(6)

print(Solution().mergeKLists([l1, l2, l3]))

print(Solution().mergeKLists([]))
print(Solution().mergeKLists([[]]))


• /**
* type ListNode struct {
*     Val int
*     Next *ListNode
* }
*/
func mergeKLists(lists []*ListNode) *ListNode {
n := len(lists)
if n == 0 {
return nil
}
for i := 1; i < n; i++ {
lists[i] = mergeTwoLists(lists[i-1], lists[i])
}
return lists[n-1]
}

func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
dummy := &ListNode{}
cur := dummy
for l1 != nil && l2 != nil {
if l1.Val <= l2.Val {
cur.Next = l1
l1 = l1.Next
} else {
cur.Next = l2
l2 = l2.Next
}
cur = cur.Next
}
if l1 != nil {
cur.Next = l1
} else if l2 != nil {
cur.Next = l2
}
return dummy.Next
}

• /**
* class ListNode {
*     val: number
*     next: ListNode | null
*     constructor(val?: number, next?: ListNode | null) {
*         this.val = (val===undefined ? 0 : val)
*         this.next = (next===undefined ? null : next)
*     }
* }
*/

function mergeKLists(lists: Array<ListNode | null>): ListNode | null {
const n = lists.length;
const dfs = (start: number, end: number) => {
if (end - start <= 1) {
return lists[start] ?? null;
}

const mid = (start + end) >> 1;
let left = dfs(start, mid);
let right = dfs(mid, end);

const dummy = new ListNode();
let cur = dummy;
while (left || right) {
let next: ListNode;
if (
(left ?? { val: Infinity }).val <
(right ?? { val: Infinity }).val
) {
next = left;
left = left.next;
} else {
next = right;
right = right.next;
}
cur.next = next;
cur = next;
}
return dummy.next;
};
return dfs(0, n);
}


• /**
* function ListNode(val, next) {
*     this.val = (val===undefined ? 0 : val)
*     this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode[]} lists
* @return {ListNode}
*/
var mergeKLists = function (lists) {
const n = lists.length;
if (n == 0) {
return null;
}
for (let i = 1; i < n; ++i) {
lists[i] = mergeTwoLists(lists[i - 1], lists[i]);
}
return lists[n - 1];
};

function mergeTwoLists(l1, l2) {
const dummy = new ListNode();
let cur = dummy;
while (l1 && l2) {
if (l1.val <= l2.val) {
cur.next = l1;
l1 = l1.next;
} else {
cur.next = l2;
l2 = l2.next;
}
cur = cur.next;
}
cur.next = l1 || l2;
return dummy.next;
}


• # Definition for singly-linked list.
# class ListNode
#     attr_accessor :val, :next
#     def initialize(val = 0, _next = nil)
#         @val = val
#         @next = _next
#     end
# end
# @param {ListNode[]} lists
# @return {ListNode}
def merge_k_lists(lists)
n = lists.length
i = 1
while i < n
lists[i] = merge_two_lists(lists[i - 1], lists[i])
i += 1
end
lists[n - 1]
end

def merge_two_lists(l1, l2)
dummy = ListNode.new()
cur = dummy
while l1 && l2
if l1.val <= l2.val
cur.next = l1
l1 = l1.next
else
cur.next = l2
l2 = l2.next
end
cur = cur.next
end
cur.next = l1 || l2
dummy.next
end

• /**
* public class ListNode {
*     public int val;
*     public ListNode next;
*     public ListNode(int val=0, ListNode next=null) {
*         this.val = val;
*         this.next = next;
*     }
* }
*/
public class Solution {
public ListNode MergeKLists(ListNode[] lists) {
int n = lists.Length;
if (n == 0) {
return null;
}
for (int i = 1; i < n; ++i) {
lists[i] = MergeTwoLists(lists[i - 1], lists[i]);
}
return lists[n - 1];
}

private ListNode MergeTwoLists(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode();
ListNode cur = dummy;
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) {
cur.next = l1;
l1 = l1.next;
} else {
cur.next = l2;
l2 = l2.next;
}
cur = cur.next;
}
cur.next = l1 == null ? l2 : l1;
return dummy.next;
}
}

• // Definition for singly-linked list.
// #[derive(PartialEq, Eq, Clone, Debug)]
// pub struct ListNode {
//   pub val: i32,
//   pub next: Option<Box<ListNode>>
// }
//
// impl ListNode {
//   #[inline]
//   fn new(val: i32) -> Self {
//     ListNode {
//       next: None,
//       val
//     }
//   }
// }
impl Solution {
pub fn merge_k_lists(mut lists: Vec<Option<Box<ListNode>>>) -> Option<Box<ListNode>> {
let n = lists.len();
Self::dfs(&mut lists, 0, n)
}

fn dfs(
lists: &mut Vec<Option<Box<ListNode>>>,
start: usize,
end: usize,
) -> Option<Box<ListNode>> {
if end - start <= 1 {
if lists.get(start).is_some() {
return lists[start].take();
}
return None;
}
let mid = start + (end - start) / 2;
let mut left = Self::dfs(lists, start, mid);
let mut right = Self::dfs(lists, mid, end);
let mut dummy = Box::new(ListNode::new(0));
let mut cur = &mut dummy;
while left.is_some() || right.is_some() {
let mut next = None;
if left.is_some()
&& (right.is_none() || left.as_ref().unwrap().val < right.as_ref().unwrap().val)
{
let t = left.as_mut().unwrap().next.take();
next = left.take();
left = t;
} else {
let t = right.as_mut().unwrap().next.take();
next = right.take();
right = t;
}
cur.next = next;
cur = cur.next.as_mut().unwrap();
}
dummy.next
}
}