Given K sorted linked lists of different sizes. The task is to merge them in such a way that after merging they will be a single sorted linked list. 
Example 1:
Input:
K = 4
value = {{1,2,3},{4 5},{5 6},{7,8}}
Output: 1 2 3 4 5 5 6 7 8
Explanation:
The test case has 4 sorted linked 
list of size 3, 2, 2, 2
1st    list     1 -> 2-> 3
2nd   list      4->5
3rd    list      5->6
4th    list      7->8
The merged list will be
1->2->3->4->5->5->6->7->8.
Example 2:
Input:
K = 3
value = {{1,3},{4,5,6},{8}}
Output: 1 3 4 5 6 8
Explanation:
The test case has 3 sorted linked
list of size 2, 3, 1.
1st list 1 -> 3
2nd list 4 -> 5 -> 6
3rd list 8
The merged list will be
1->3->4->5->6->8.
Your Task:
The task is to complete the function mergeKList() which merges the K given lists into a sorted one. The printing is done automatically by the driver code.
Expected Time Complexity: O(nk Logk)
Expected Auxiliary Space: O(k)
Note: n is the maximum size of all the k link list
Constraints
1 <= K <= 10^{3}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Data structures

Starter code: #User function Template for python3

'''

	Your task is to merge the given k sorted

	linked lists into one list and return

	the the new formed linked list class.



	Function Arguments:

	    arr is a list containing the n linkedlist head pointers

	    n is an integer value

    

    node class:

    

class Node:

    def __init__(self,x):

        self.data = x

        self.next = None

'''

class Solution:

    #Function to merge K sorted linked list.

    def mergeKLists(self,arr,K):

        # code here

        # return head of merged list

Solutions:
import heapq

class Solution:

	def mergeKLists(self, arr, K):
		dummy = Node(-1)
		heap = []
		for i in arr:
			while i:
				heapq.heappush(heap, i.data)
				i = i.next
		ptr = dummy
		while heap:
			temp = Node(heapq.heappop(heap))
			ptr.next = temp
			ptr = ptr.next
		ptr.next = None
		return dummy.next


import heapq

class Solution:

	def mergeKLists(self, arr, K):
		n = len(arr)
		heap = []
		heapq.heapify(heap)
		for i in range(n):
			if arr[i]:
				temp_val = arr[i].data
				arr[i] = arr[i].next
				heapq.heappush(heap, [temp_val, i])
		head = Node(0)
		node = head
		while heap:
			(val, ind) = heapq.heappop(heap)
			node_i = Node(val)
			node.next = node_i
			node = node.next
			if arr[ind]:
				temp_val = arr[ind].data
				arr[ind] = arr[ind].next
				heapq.heappush(heap, [temp_val, ind])
		return head.next


class Solution:

	def mergeKLists(self, arr, K):
		res = []
		for i in range(K):
			while arr[i]:
				res.append(arr[i].data)
				arr[i] = arr[i].next
		res.sort()
		head = Node(res[0])
		tail = head
		for i in range(1, len(res)):
			temp = Node(res[i])
			tail.next = temp
			tail = temp
		return head


import heapq

class Solution:

	def mergeKLists(self, lists, K):
		heap = []
		for i in range(len(lists)):
			if lists[i]:
				heap.append((lists[i].data, i))
				lists[i] = lists[i].next
		heapq.heapify(heap)
		merged_head = Node(None)
		curr = merged_head
		while heap:
			(minVal, listIndex) = heapq.heappop(heap)
			curr.next = Node(minVal)
			curr = curr.next
			if lists[listIndex]:
				heapq.heappush(heap, (lists[listIndex].data, listIndex))
				lists[listIndex] = lists[listIndex].next
		return merged_head.next


class Solution:

	def mergeKLists(self, arr, K):
		li = []
		link1 = link2 = Node(0)
		for n in arr:
			while n:
				li.append(n)
				n = n.next
		li.sort(key=lambda x: x.data)
		for n in li:
			link1.next = n
			link1 = link1.next
		return link2.next


class Solution:

	def mergeKLists(self, arr, K):
		c = K
		while c > 1:
			front1 = arr.pop(0)
			front2 = arr.pop(0)
			res = None
			res_head = None
			while front1 is not None and front2 is not None:
				if front1.data < front2.data:
					if res_head is None:
						res_head = front1
						res = front1
					else:
						res.next = front1
						res = res.next
					front1 = front1.next
				else:
					if res_head is None:
						res_head = front2
						res = front2
					else:
						res.next = front2
						res = res.next
					front2 = front2.next
			if front1 is not None:
				res.next = front1
			if front2 is not None:
				res.next = front2
			arr.append(res_head)
			c -= 1
		return arr[0]


import heapq

class Solution:

	def mergeKLists(self, arr, K):
		min_heap = []
		for i in range(K):
			if arr[i]:
				heapq.heappush(min_heap, (arr[i].data, i))
		result_head = Node(0)
		current = result_head
		while min_heap:
			(val, index) = heapq.heappop(min_heap)
			current.next = Node(val)
			current = current.next
			if arr[index].next:
				arr[index] = arr[index].next
				heapq.heappush(min_heap, (arr[index].data, index))
		return result_head.next


class Solution:

	def mergeKLists(self, arr, K):
		interval = 1
		while interval < K:
			for i in range(0, K - interval, interval * 2):
				arr[i] = self.merge2List(arr[i], arr[i + interval])
			interval *= 2
		return arr[0]

	def merge2List(self, l1, l2):
		if l1 is None:
			return l2
		if l2 is None:
			return l1
		if l1.data > l2.data:
			(l1, l2) = (l2, l1)
		res = l1
		while l1 and l2:
			tmp = None
			while l1 != None and l1.data <= l2.data:
				tmp = l1
				l1 = l1.next
			tmp.next = l2
			(l1, l2) = (l2, l1)
		return res


class Solution:

	def mergeKLists(self, arr, K):
		list1 = []
		linked1 = linked2 = Node(0)
		for n in arr:
			while n:
				list1.append(n)
				n = n.next
		list1.sort(key=lambda x: x.data)
		for n in list1:
			linked1.next = n
			linked1 = linked1.next
		return linked2.next


from heapq import *

class Solution:

	def mergeKLists(self, arr, k):
		heap = []
		for i in range(len(arr)):
			heappush(heap, (arr[i].data, i))
			arr[i] = arr[i].next
		start = None
		while k > 0:
			elm = heappop(heap)
			node = Node(elm[0])
			if start is None:
				start = node
			else:
				temp.next = node
			temp = node
			if arr[elm[1]]:
				heappush(heap, (arr[elm[1]].data, elm[1]))
				arr[elm[1]] = arr[elm[1]].next
			else:
				k -= 1
		return start


from heapq import *

class Solution:

	def mergeKLists(self, arr, k):
		heap = []
		for i in range(k):
			heappush(heap, (arr[i].data, i))
			arr[i] = arr[i].next
		new = Node(-1)
		temp = new
		while len(heap) != 0:
			(data, index) = heappop(heap)
			node = Node(data)
			temp.next = node
			temp = temp.next
			if arr[index]:
				heappush(heap, (arr[index].data, index))
				arr[index] = arr[index].next
		return new.next


class Solution:

	def mergeKLists(self, arr, K):
		if len(arr) == 0:
			return None
		while len(arr) > 1:
			merged_list = []
			for i in range(0, len(arr), 2):
				l1 = arr[i]
				l2 = arr[i + 1] if i + 1 < len(arr) else None
				merged_list.append(self.mergelist(l1, l2))
			arr = merged_list
		return arr[0]

	def mergelist(self, l1, l2):
		head = Node(0)
		tmp = head
		while l1 and l2:
			if l1.data < l2.data:
				tmp.next = l1
				l1 = l1.next
			else:
				tmp.next = l2
				l2 = l2.next
			tmp = tmp.next
		if l1:
			tmp.next = l1
		if l2:
			tmp.next = l2
		return head.next


class Solution:

	def mergeKLists(self, arr, K):
		a = []
		for i in arr:
			ans = []
			cur = i
			while cur:
				ans.append(cur.data)
				cur = cur.next
			a.extend(ans)
		a.sort()
		n = Node(0)
		h = n
		for i in a:
			k = Node(i)
			n.next = k
			n = n.next
		return h.next


class Solution:

	def mergeSort(self, h1, h2):
		dummyNode = Node(0)
		tail = dummyNode
		while True:
			if h1 is None:
				tail.next = h2
				break
			if h2 is None:
				tail.next = h1
				break
			if h1.data <= h2.data:
				tail.next = h1
				h1 = h1.next
			else:
				tail.next = h2
				h2 = h2.next
			tail = tail.next
		return dummyNode.next

	def mergeKLists(self, arr, K):
		last = K - 1
		while last != 0:
			i = 0
			j = last
			while i < j:
				arr[i] = self.mergeSort(arr[i], arr[j])
				i += 1
				j -= 1
				if i >= j:
					last = j
		return arr[0]


import heapq

class Solution:

	def mergeKLists(self, arr, K):
		brr = []
		for i in range(K):
			while arr[i] != None:
				brr.append(arr[i].data)
				arr[i] = arr[i].next
		brr.sort()
		head = Node(brr[0])
		tail = head
		for i in range(1, len(brr)):
			temp = Node(brr[i])
			tail.next = temp
			tail = temp
		return head


import heapq

class Node:

	def __init__(self, x):
		self.data = x
		self.next = None

	def __lt__(self, nxt):
		return self.data < nxt.data

class Solution:

	def mergeKLists(self, arr, K):
		try:
			min_heap = []
			idx = 0
			for i in range(K):
				heapq.heappush(min_heap, (arr[i].data, idx, arr[i]))
				idx += 1
			new_head = new_tail = None
			while min_heap:
				(data, _, node) = heapq.heappop(min_heap)
				if new_head is None:
					new_head = node
					new_tail = node
				else:
					new_tail.next = node
					new_tail = node
				if node.next:
					idx += 1
					heapq.heappush(min_heap, (node.next.data, idx, node.next))
			new_tail.next = None
			return new_head
		except Exception as e:
			print('Error: ', e)


class Solution:

	def mergeKLists(self, arr, K):
		llarr = []
		for i in arr:
			h = i
			while h:
				llarr.append(h.data)
				h = h.next
		llarr.sort()
		dummy = Node(-1)
		head = dummy
		for i in llarr:
			nextNode = Node(i)
			head.next = nextNode
			head = nextNode
		return dummy.next


class Solution:

	def mergeKLists(self, arr, K):
		l = []

		def add(head):
			if head == None:
				return
			while head != None:
				l.append(head.data)
				head = head.next
		for i in range(K):
			add(arr[i])
		l.sort()
		a = Node(0)
		b = a
		for i in range(len(l)):
			a.next = Node(l[i])
			a = a.next
		return b.next


class Solution:

	def mergeKLists(self, arr, K):
		lis = []
		for i in arr:
			while i:
				lis.append(i.data)
				i = i.next
		lis.sort()
		tempp = Node(0)
		thead = tempp
		for i in lis:
			temp = Node(i)
			tempp.next = temp
			tempp = tempp.next
		return thead.next


class Solution:

	def mergeKLists(self, arr, K):
		L = []
		for i in arr:
			n = i
			while n is not None:
				L.append(n.data)
				n = n.next
		L.sort()
		new = Node(0)
		n = new
		while L:
			new_node = Node(L.pop(0))
			n.next = new_node
			n = n.next
		return new.next


def merge(head1, head2):
	if head1 is None:
		return head2
	if head2 is None:
		return head1
	ans = Node(-1)
	temp = ans
	while head1 != None and head2 != None:
		if head1.data < head2.data:
			temp.next = head1
			temp = head1
			head1 = head1.next
		else:
			temp.next = head2
			temp = head2
			head2 = head2.next
	while head1 != None:
		temp.next = head1
		temp = head1
		head1 = head1.next
	while head2 != None:
		temp.next = head2
		temp = head2
		head2 = head2.next
	ans = ans.next
	return ans

def mergeList(arr, si, ei):
	if arr[si] == arr[ei]:
		return arr[si]
	mid = (si + ei) // 2
	list1 = mergeList(arr, mid + 1, ei)
	list2 = mergeList(arr, si, mid)
	return merge(list1, list2)

class Solution:

	def mergeKLists(self, arr, K):
		if len(arr) == 0:
			return None
		return mergeList(arr, 0, len(arr) - 1)


from heapq import heapify, heappop, heappush

class Solution:

	def mergeKLists(self, arr, K):
		res = []
		for i in arr:
			node = i
			while node is not None:
				heappush(res, node.data)
				node = node.next
		ll = LinkedList()
		head = Node(heappop(res))
		ll.head = head
		node = head
		while res:
			temp = Node(heappop(res))
			node.next = temp
			node = temp
		return head


class Solution:

	def mergeKLists(self, arr, K):
		return self.mergeSort(0, K - 1, arr)

	def mergeSort(self, l, h, arr):
		if l < h:
			m = (l + h) // 2
			arr[l] = self.mergeSort(l, m, arr)
			arr[h] = self.mergeSort(m + 1, h, arr)
			arr[l] = arr[h] = self.merge(arr[l], arr[h], arr)
		return arr[l]

	def merge(self, temp1, temp2, arr):
		head = Node(0)
		temp = head
		while temp1 is not None and temp2 is not None:
			if temp1.data < temp2.data:
				temp.next = temp1
				temp1 = temp1.next
			else:
				temp.next = temp2
				temp2 = temp2.next
			temp = temp.next
		if temp1 is None:
			temp.next = temp2
		else:
			temp.next = temp1
		temp = head
		head = head.next
		del temp
		return head


from queue import PriorityQueue

class Node:

	def __init__(self, data):
		self.data = data
		self.next = None

def merge_k_sorted_linked_list(input_arr: [Node], k):
	final_head = None
	curr = None
	data_queue = PriorityQueue()
	for i in range(k):
		head = input_arr[i]
		data_queue.put((head.data, i, head))
	while len(data_queue.queue) > 0:
		element_data = data_queue.get()
		element_popped = element_data[2]
		if final_head is None:
			final_head = element_popped
			curr = element_popped
		else:
			temp = curr
			temp.next = element_popped
			curr = element_popped
		if element_popped.next is not None:
			next_element = element_popped.next
			list_number = element_data[1]
			data_queue.put((next_element.data, list_number, next_element))
	return final_head

class Solution:

	def mergeKLists(self, arr, k):
		return merge_k_sorted_linked_list(arr, k)


class Solution:

	def mergeKLists(self, arr, K):
		fl = []
		for i in range(K):
			s = arr[i]
			l = []
			while s != None:
				l.append(s.data)
				s = s.next
			fl.extend(l)
		fl.sort(reverse=True)
		head = None
		for i in fl:
			n = Node(i)
			if head == None:
				head = n
			else:
				n.next = head
				head = n
		return head


class Solution:

	def mergeKLists(self, lists, K):
		numslist = []
		for lst in lists:
			while True:
				if lst:
					numslist.append(lst.data)
					lst = lst.next
				else:
					break
		numslist.sort()
		head = None
		res = None
		for num in numslist:
			if head:
				currNode = Node(num)
				head.next = currNode
				head = head.next
			else:
				head = Node(num)
				res = head
		return res


class Solution:

	def mergeKLists(self, lists, K):

		def mergealgo(curr1, curr2):
			head = Node(0)
			temp = head
			if not curr1:
				return curr2
			if not curr2:
				return curr1
			while curr1 and curr2:
				if curr1.data >= curr2.data:
					temp.next = curr2
					temp = curr2
					curr2 = curr2.next
				else:
					temp.next = curr1
					temp = curr1
					curr1 = curr1.next
			if curr1:
				temp.next = curr1
			else:
				temp.next = curr2
			head = head.next
			return head
		k = len(lists)
		i = 2
		if k == 0:
			return None
		if k == 1:
			return lists[-1]
		ans = mergealgo(lists[0], lists[1])
		while i < k:
			ans = mergealgo(ans, lists[i])
			i += 1
		return ans


class Solution:

	def mergeKLists(self, arr, K):
		l = []
		for i in arr:
			while i:
				l.append(i.data)
				i = i.next
		l.sort()
		ll = LinkedList()
		for i in l:
			ll.add(i)
		return ll.head


class Solution:

	def mergeKLists(self, arr, k):
		lis = []
		p = 0
		c = 0
		i = 0
		arr[i]
		while i < k:
			temp = arr[i]
			while temp != None:
				c += 1
				temp = temp.next
			i += 1
		while c > 0:
			for i in range(k):
				temp = arr[i]
				if temp != None:
					lis.append(temp.data)
					temp = temp.next
					arr[i] = temp
			c -= 1
		if lis:
			lis.sort()
		new = Node(lis[0])
		head = new
		for i in range(1, len(lis)):
			node = Node(lis[i])
			new.next = node
			new = node
		new.next = None
		return head


import heapq

class Solution:

	def mergeKLists(self, arr, K):
		hp = []
		i = 0
		for el in arr:
			heapq.heappush(hp, [el.data, i, el.next])
			i += 1
		ans = Node(1)
		a = ans
		while hp:
			p = heapq.heappop(hp)
			a.next = Node(p[0])
			a = a.next
			if p[2]:
				heapq.heappush(hp, [p[2].data, i, p[2].next])
				i += 1
		return ans.next


class Solution:

	def mergeKLists(self, arr, K):
		l = []
		if len(arr) == 0:
			return -1
		for i in range(K):
			h = arr[i]
			while h:
				l.append(h.data)
				h = h.next
		l = sorted(l)
		if len(l) == 0:
			return -1
		head = Node(l[0])
		t = head
		for i in range(1, len(l)):
			temp = Node(l[i])
			t.next = temp
			t = temp
		return head


import heapq

class Solution:

	def mergeKLists(self, arr, K):
		head = Node(None)
		curr = head
		minheap = []
		for i in range(len(arr)):
			if arr[i]:
				heapq.heappush(minheap, (arr[i].data, i))
				arr[i] = arr[i].next
		while minheap:
			(val, i) = heapq.heappop(minheap)
			curr.next = Node(val)
			curr = curr.next
			if arr[i]:
				heapq.heappush(minheap, (arr[i].data, i))
				arr[i] = arr[i].next
		return head.next


class Solution:

	def mergeKLists(self, arr, k):
		final = None
		start = None
		for i in range(k // 2 - 1, -1, -1):
			self.downHeap(arr, k, i)
		while k:
			if start == None:
				start = arr[0]
				final = arr[0]
			else:
				final.next = arr[0]
				final = final.next
			if arr[0].next:
				arr[0] = arr[0].next
			else:
				(arr[0], arr[k - 1]) = (arr[k - 1], arr[0])
				k -= 1
			self.downHeap(arr, k, 0)
		return start

	def downHeap(self, arr, k, i):
		smallest = i
		if i * 2 + 1 < k and arr[smallest].data > arr[i * 2 + 1].data:
			smallest = 2 * i + 1
		if i * 2 + 2 < k and arr[smallest].data > arr[i * 2 + 2].data:
			smallest = 2 * i + 2
		if smallest != i:
			(arr[i], arr[smallest]) = (arr[smallest], arr[i])
			self.downHeap(arr, k, smallest)


class Node:

	def __init__(self, x):
		self.data = x
		self.next = None

def merge(head1, head2):
	tmp = temp = None
	while head1 and head2:
		if head1.data <= head2.data:
			if not tmp:
				temp = head1
				tmp = head1
			else:
				tmp.next = head1
				tmp = tmp.next
			head1 = head1.next
		else:
			if not tmp:
				temp = head2
				tmp = head2
			else:
				tmp.next = head2
				tmp = tmp.next
			head2 = head2.next
	while head1:
		tmp.next = head1
		tmp = tmp.next
		head1 = head1.next
	while head2:
		tmp.next = head2
		tmp = tmp.next
		head2 = head2.next
	return temp

class Solution:

	def mergeKLists(self, arr, K):
		tmp = arr[0]
		for i in range(1, len(arr)):
			tmp = merge(tmp, arr[i])
		return tmp


class Solution:

	def merge(self, head1, head2):
		if head1 == None and head2 == None:
			return head1
		elif head1 != None and head2 == None:
			return head1
		elif head1 == None and head2 != None:
			return head2
		new_head = None
		(itr1, itr2) = (head1, head2)
		if itr1.data < itr2.data:
			new_head = head1
			itr1 = itr1.next
		else:
			new_head = head2
			itr2 = itr2.next
		temp = new_head
		while itr1 and itr2:
			if itr1.data < itr2.data:
				temp.next = itr1
				itr1 = itr1.next
			else:
				temp.next = itr2
				itr2 = itr2.next
			temp = temp.next
		while itr1:
			temp.next = itr1
			itr1 = itr1.next
			temp = temp.next
		while itr2:
			temp.next = itr2
			itr2 = itr2.next
			temp = temp.next
		return new_head

	def mergeKLists(self, arr, K):
		head = None
		for i in range(0, len(arr)):
			head = self.merge(head, arr[i])
		return head


class Solution:

	def mergeKLists(self, lists, k):

		def merge(head1, head2):
			dummy = Node(-1)
			tail = dummy
			curr1 = head1
			curr2 = head2
			while curr1 != None and curr2 != None:
				if curr1.data < curr2.data:
					tail.next = curr1
					curr1 = curr1.next
				else:
					tail.next = curr2
					curr2 = curr2.next
				tail = tail.next
			if curr1 == None:
				tail.next = curr2
			elif curr2 == None:
				tail.next = curr1
			return dummy.next
		i = 0
		last = k - 1
		while last != 0:
			i = 0
			j = last
			while i < j:
				lists[i] = merge(lists[i], lists[j])
				i += 1
				j -= 1
				if i >= j:
					last = j
		return lists[0]


class Solution:

	def mergeKLists(self, lists, k):

		def merge(head1, head2):
			hf = None
			ht = None
			while head1 != None and head2 != None:
				if ht == None and hf == None:
					if head1.data < head2.data:
						hf = head1
						ht = head1
						head1 = head1.next
					else:
						ht = head2
						hf = head2
						head2 = head2.next
				elif head1.data < head2.data:
					ht.next = head1
					ht = ht.next
					head1 = head1.next
				else:
					ht.next = head2
					ht = ht.next
					head2 = head2.next
			if head1 != None:
				ht.next = head1
			if head2 != None:
				ht.next = head2
			return hf
		i = 0
		last = k - 1
		while last != 0:
			i = 0
			j = last
			while i < j:
				lists[i] = merge(lists[i], lists[j])
				i += 1
				j -= 1
				if i >= j:
					last = j
		return lists[0]


import heapq as hq

class Solution:

	def findMin(self, arr, K):
		least = float('inf')
		node = None
		index = -1
		for i in range(K):
			h = arr[i]
			if h is not None:
				if h.data < least:
					least = h.data
					node = h
					index = i
		return (node, index)

	def mergeKLists(self, arr, K):
		arr1 = [(a.data, id(a), a) for a in arr]
		hq.heapify(arr1)
		newHead = Node(None)
		temp = newHead
		while True:
			(data, iD, node) = hq.heappop(arr1)
			temp.next = node
			temp = temp.next
			if node.next is not None:
				hq.heappush(arr1, (node.next.data, id(node.next), node.next))
			elif len(arr1) == 0:
				break
		return newHead.next


class Solution:

	def findMin(self, arr, K):
		least = float('inf')
		node = None
		index = -1
		for i in range(K):
			h = arr[i]
			if h is not None:
				if h.data < least:
					least = h.data
					node = h
					index = i
		return (node, index)

	def mergeKLists(self, arr, K):
		newHead = Node(None)
		temp = newHead
		while True:
			(node, index) = self.findMin(arr, K)
			temp.next = node
			temp = temp.next
			if node is not None:
				arr[index] = node.next
			else:
				break
		return newHead.next


class Solution:

	def mergeKLists(self, arr, K):

		def sortedMerge(head1, head2):
			t = g = Node(0)
			g.next = head1 if head1.data < head2.data else head2
			while head1 and head2:
				if head1.data < head2.data:
					t.next = head1
					head1 = head1.next
					t = t.next
				else:
					t.next = head2
					head2 = head2.next
					t = t.next
			t.next = head1 if head1 else head2
			return g.next
		for i in range(1, K):
			arr[0] = sortedMerge(arr[0], arr[i])
		return arr[0]


class Solution:

	def mergeKLists(self, arr, K):
		if not arr or len(arr) == 0:
			return None
		while len(arr) > 1:
			mergedLists = []
			for i in range(0, len(arr), 2):
				l1 = arr[i]
				l2 = arr[i + 1] if i + 1 < len(arr) else None
				mergedLists.append(self.mergeList(l1, l2))
			arr = mergedLists
		return arr[0]

	def mergeList(self, l1, l2):
		dummy = Node(0)
		tail = dummy
		while l1 and l2:
			if l1.data < l2.data:
				tail.next = l1
				l1 = l1.next
			else:
				tail.next = l2
				l2 = l2.next
			tail = tail.next
		if l1:
			tail.next = l1
		if l2:
			tail.next = l2
		return dummy.next


class Node:

	def __init__(self, x):
		self.data = x
		self.next = None

class Solution:

	def mergeKLists(self, arr, K):
		l = []
		for i in arr:
			while i is not None:
				l += [i.data]
				i = i.next
		l = sorted(l)
		head = Node(l[0])
		n = head
		for i in range(1, len(l)):
			no = Node(l[i])
			n.next = no
			no.next = None
			n = n.next
		return head


class Solution:

	def mergeKLists(self, arr, K):
		merged = Node(0)
		tmp = merged
		heap = []
		import heapq
		for i in range(len(arr)):
			if arr[i]:
				heapq.heappush(heap, (arr[i].data, i, arr[i]))
		while heap:
			(data, i, node) = heapq.heappop(heap)
			tmp.next = node
			tmp = tmp.next
			if node.next:
				heapq.heappush(heap, (node.next.data, i, node.next))
		return merged.next


class Solution:

	def merge(self, ll1, ll2):
		if ll1 is None:
			return ll2
		if ll2 is None:
			return ll1
		if ll1.data > ll2.data:
			head = ll2
			tail = ll2
			ll2 = ll2.next
		else:
			head = ll1
			tail = ll1
			ll1 = ll1.next
		while ll1 is not None and ll2 is not None:
			if ll1.data > ll2.data:
				tail.next = ll2
				tail = ll2
				ll2 = ll2.next
			else:
				tail.next = ll1
				tail = ll1
				ll1 = ll1.next
		while ll1 is not None:
			tail.next = ll1
			tail = ll1
			ll1 = ll1.next
		while ll2 is not None:
			tail.next = ll2
			tail = ll2
			ll2 = ll2.next
		tail.next = None
		return head

	def mergeKLists(self, lists, K):
		for i in range(1, len(lists)):
			lists[i] = self.merge(lists[i], lists[i - 1])
		return lists[-1]


import heapq

class Solution:

	def mergeKLists(self, arr, K):
		queue = []
		for i in range(K):
			if arr[i] != None:
				heapq.heappush(queue, (arr[i].data, id(arr[i]), arr[i]))
		dummy = Node(0)
		last = dummy
		while queue:
			curr = heapq.heappop(queue)[2]
			last.next = curr
			last = last.next
			if curr.next != None:
				heapq.heappush(queue, (curr.next.data, id(curr), curr.next))
		return dummy.next


import heapq

class Solution:

	def mergeKLists(self, arr, K):
		heap = []
		for i in range(K):
			if arr[i]:
				heapq.heappush(heap, (arr[i].data, i, arr[i]))
		dummy = Node(0)
		curr = dummy
		while heap:
			(val, index, node) = heapq.heappop(heap)
			curr.next = node
			curr = curr.next
			if node.next:
				heapq.heappush(heap, (node.next.data, index, node.next))
		return dummy.next


class Solution:

	def mergeKLists(self, arr, K):
		l = []
		for i in arr:
			itr = i
			while itr:
				l.append(itr.data)
				itr = itr.next
		l.sort()
		for i in l:
			print(i, end=' ')


class Solution:

	def mergeKLists(self, arr, K):

		def sortedMerge(head1, head2):
			curr1 = head1
			curr2 = head2
			ans = Node(None)
			curr = Node(None)
			if curr1 != None and curr2 == None:
				ans = curr1
				return ans
			if curr2 != None and curr1 == None:
				ans = curr2
				return ans
			while curr1 != None and curr2 != None:
				if curr1.data <= curr2.data:
					if ans.data == None:
						ans.data = curr1.data
						curr = ans
						curr1 = curr1.next
					else:
						ans.next = curr1
						ans = ans.next
						curr1 = curr1.next
				elif ans.data == None:
					ans.data = curr2.data
					curr = ans
					curr2 = curr2.next
				else:
					ans.next = curr2
					ans = ans.next
					curr2 = curr2.next
			if curr1 != None:
				ans.next = curr1
			if curr2 != None:
				ans.next = curr2
			return curr
		if not arr or len(arr) == 0:
			return None
		while len(arr) > 1:
			mergedList = []
			for i in range(0, len(arr), 2):
				l1 = arr[i]
				l2 = arr[i + 1] if i + 1 < len(arr) else None
				mergedList.append(sortedMerge(l1, l2))
			arr = mergedList
		return arr[0]


class Solution:

	def mergeKLists(self, arr, K):
		if len(arr) == 0 or not arr:
			return None
		while len(arr) > 1:
			mergedlist = []
			for i in range(0, len(arr), 2):
				l1 = arr[i]
				l2 = arr[i + 1] if len(arr) > i + 1 else None
				mergedlist.append(self.mergelist(l1, l2))
			arr = mergedlist
		return arr[0]

	def mergelist(self, l1, l2):
		x = Node(0)
		dummy = x
		while l1 and l2:
			if l1.data < l2.data:
				dummy.next = l1
				l1 = l1.next
			else:
				dummy.next = l2
				l2 = l2.next
			dummy = dummy.next
		if l1:
			dummy.next = l1
		else:
			dummy.next = l2
		return x.next


class Solution:

	def mergeKLists(self, arr, K):
		l = []
		for i in arr:
			temp = i
			while temp:
				l.append(temp.data)
				temp = temp.next
		l.sort()
		h = Node(0)
		p = h
		for i in l:
			p.next = Node(i)
			p = p.next
		return h.next


class Solution:

	def MergeLists(self, n1, n2):
		ret = None
		if n2.data < n1.data:
			ret = n2
			n2 = n2.next
		else:
			ret = n1
			n1 = n1.next
		tail = ret
		while n1 is not None and n2 is not None:
			if n2.data < n1.data:
				tail.next = n2
				tail = n2
				n2 = n2.next
			else:
				tail.next = n1
				tail = n1
				n1 = n1.next
		if n1:
			tail.next = n1
		if n2:
			tail.next = n2
		return ret

	def mergeKLists(self, arr, K):
		N = K
		last = N - 1
		while last != 0:
			i = 0
			j = last
			while i < j:
				arr[i] = self.MergeLists(arr[i], arr[j])
				i += 1
				j -= 1
				if i >= j:
					last = j
		return arr[0]


class Solution:

	def mergeKLists(self, arr, K):
		while len(arr) > 1:
			temp = []
			for i in range(0, len(arr), 2):
				one = arr[i]
				two = arr[i + 1] if len(arr) > i + 1 else None
				temp += [vamsi(one, two)]
			arr[:] = temp
		return arr[0]

def vamsi(one, two):
	s = Node(0)
	ans = s
	while one and two:
		if one.data < two.data:
			ans.next = Node(one.data)
			one = one.next
		else:
			ans.next = Node(two.data)
			two = two.next
		ans = ans.next
	ans.next = one or two
	return s.next


class Solution:

	def mergeKLists(self, arr, K):
		r = []
		for i in arr:
			while i != None:
				r.append(i.data)
				i = i.next
		r.sort()
		ans = Node(0)
		d = ans
		for i in r:
			d.next = Node(i)
			d = d.next
		return ans.next


import heapq

class Solution:

	def mergeKLists(self, arr, K):
		count = 0
		heap = []
		for i in range(K):
			heapq.heappush(heap, (arr[i].data, count, arr[i]))
			count += 1
		head = tail = None
		while len(heap):
			(data, _, node) = heapq.heappop(heap)
			if head == None:
				head = tail = node
			else:
				tail.next = node
				tail = node
			if tail.next:
				heapq.heappush(heap, (tail.next.data, count, tail.next))
				count += 1
		return head


class Solution:

	def LinktoArray(self, head):
		c = []
		cur = head
		while cur:
			c.append(cur.data)
			cur = cur.next
		return c

	def ArraytoLink(self, arr):
		dum = Node(0)
		ans = dum
		for i in range(len(arr)):
			ans.next = Node(arr[i])
			ans = ans.next
		return dum.next

	def mergeKLists(self, arr, K):
		con = []
		for i in arr:
			x = self.LinktoArray(i)
			con += x
		con.sort()
		head = self.ArraytoLink(con)
		return head


class Solution:

	def mergeKLists(self, arr, K):
		if K == 1:
			return arr[0]
		lis = []
		for i in range(K):
			node = arr[i]
			while node:
				lis.append(node.data)
				node = node.next
		lis = sorted(lis)
		head = Node(lis[0])
		node = head
		for i in lis[1:]:
			node.next = Node(i)
			node = node.next
		return head


class Solution:

	def mergeKLists(self, arr, K):

		def _mergeKLists(k):
			if k == K - 1:
				return arr[k]
			else:
				l1 = _mergeKLists(k + 1)
				l2 = arr[k]
				return self.merge(l1, l2)
		return _mergeKLists(0)

	def merge(self, l1, l2):
		result = rc = None
		curr1 = l1
		curr2 = l2
		while curr1 and curr2:
			if curr1.data <= curr2.data:
				if not result:
					result = rc = curr1
					curr1 = curr1.next
				else:
					nxt1 = rc.next
					nxt2 = curr1.next
					rc.next = curr1
					if nxt1 != curr1:
						curr1.next = nxt1
					curr1 = nxt2
					rc = rc.next
			elif not result:
				result = rc = Node(curr2.data)
				curr2 = curr2.next
			else:
				nxt1 = rc.next
				nxt2 = curr2.next
				rc.next = curr2
				if nxt1 != curr2:
					curr2.next = nxt1
				curr2 = nxt2
				rc = rc.next
		while curr1:
			rc.next = curr1
			rc = rc.next
			curr1 = curr1.next
		while curr2:
			rc.next = curr2
			rc = rc.next
			curr2 = curr2.next
		return result


class Solution:

	def mergeKLists(self, arr, K):

		def merge(h1, h2):
			(p1, p2) = (h1, h2)
			ans = Node(-1)
			a = ans
			while p1 and p2:
				if p1.data < p2.data:
					a.next = p1
					a = a.next
					p1 = p1.next
				else:
					a.next = p2
					a = a.next
					p2 = p2.next
			while p1:
				a.next = p1
				a = a.next
				p1 = p1.next
			while p2:
				a.next = p2
				a = a.next
				p2 = p2.next
			return ans.next
		ans = arr[0]
		for i in range(1, len(arr)):
			ans = merge(ans, arr[i])
		return ans


class Solution:

	def mergeKLists(self, arr, K):
		a = []
		for x in arr:
			curr = x
			while curr != None:
				a.append(curr.data)
				curr = curr.next
		a.sort()
		head = Node(None)
		temp = head
		for x in a:
			temp.next = Node(x)
			temp = temp.next
		return head.next


class Solution:

	def mergeKLists(self, lists, K):

		def merger(l1, l2):
			res = Node(0)
			cur = res
			while l1 and l2:
				if l1.data >= l2.data:
					cur.next = l2
					l2 = l2.next
				else:
					cur.next = l1
					l1 = l1.next
				cur = cur.next
			if not l1:
				cur.next = l2
			else:
				cur.next = l1
			return res.next
		n = len(lists)
		if n <= 0:
			return None
		jump = 1
		while jump < n:
			for i in range(0, n - jump, jump * 2):
				lists[i] = merger(lists[i], lists[i + jump])
			jump *= 2
		return lists[0]


class Solution:

	def mergeKLists(self, arr, K):
		if not arr:
			return None
		if len(arr) == 1:
			return arr[0]
		mid = len(arr) // 2
		l = self.mergeKLists(arr[:mid], K)
		r = self.mergeKLists(arr[mid:], K)
		return self.merge(l, r)

	def merge(self, l1, l2):
		dummy = LinkedList()
		curr = dummy
		while l1 and l2:
			if l1.data < l2.data:
				curr.next = l1
				l1 = l1.next
			else:
				curr.next = l2
				l2 = l2.next
			curr = curr.next
		curr.next = l1 or l2
		return dummy.next


class Solution:

	def mergeKLists(self, arr, K):
		lists = arr

		def merged(list1, list2):
			curr1 = list1
			curr2 = list2
			new_node = Node(0)
			tmp = new_node
			while curr1 and curr2:
				if curr1.data <= curr2.data:
					tmp.next = curr1
					tmp = tmp.next
					curr1 = curr1.next
				else:
					tmp.next = curr2
					tmp = tmp.next
					curr2 = curr2.next
			if curr1:
				tmp.next = curr1
			else:
				tmp.next = curr2
			return new_node.next
		res = Node(0)
		x = []
		i = 0
		if len(lists) < 1:
			return None
		if len(lists) == 1:
			return lists[0]
		while i < len(lists):
			if i == 0:
				res = merged(lists[0], lists[1])
				i += 2
			else:
				res = merged(res, lists[i])
				i += 1
		return res


class Solution:

	def mergeKLists(self, arr, K):
		if len(arr) == 1:
			return arr[0]
		while len(arr) > 1:
			list1 = arr.pop(0) if len(arr) > 0 else None
			list2 = arr.pop(0) if len(arr) > 0 else None
			mergedList = self.mergeList(list1, list2)
			arr.append(mergedList)
		return arr[0]

	def mergeList(self, list1, list2):
		listNode = Node(0)
		dummy = listNode
		(temp1, temp2) = (list1, list2)
		while temp1 and temp2:
			if temp1.data < temp2.data:
				dummy.next = temp1
				dummy = dummy.next
				temp1 = temp1.next
			else:
				dummy.next = temp2
				dummy = dummy.next
				temp2 = temp2.next
		while temp1:
			dummy.next = temp1
			dummy = dummy.next
			temp1 = temp1.next
		while temp2:
			dummy.next = temp2
			dummy = dummy.next
			temp2 = temp2.next
		return listNode.next


class Solution:

	def mergeKLists(self, arr, K):
		while len(arr) > 1:
			mergedList = []
			for i in range(0, len(arr), 2):
				l1 = arr[i]
				l2 = arr[i + 1] if i + 1 < len(arr) else None
				mergedList.append(self.mergeList(l1, l2))
			arr = mergedList
		return arr[0]

	def mergeList(self, l1, l2):
		head = tail = Node(0)
		while l1 and l2:
			if l1.data < l2.data:
				tail.next = l1
				l1 = l1.next
			else:
				tail.next = l2
				l2 = l2.next
			tail = tail.next
		tail.next = l1 if l1 else l2
		return head.next


class Solution:

	def mergeKLists(self, arr, K):
		store = []
		for x in arr:
			cur = x
			while cur != None:
				store.append(cur.data)
				cur = cur.next
		store = sorted(store)
		head = Node(-1)
		temp = head
		for x in store:
			temp.next = Node(x)
			temp = temp.next
		return head.next


class Solution:

	def mergeKLists(self, arr, K):
		store = []
		for llist in arr:
			curr = llist
			while curr != None:
				store.append(curr.data)
				curr = curr.next
		store = sorted(store)
		head1 = Node(-1)
		tmp = head1
		for element in store:
			tmp.next = Node(element)
			tmp = tmp.next
		return head1.next


import heapq

class node:

	def __init__(self, data, value):
		self.data = data
		self.value = value

	def __lt__(self, other):
		return self.data > other.data

class Solution:

	def mergeKLists(self, arr, K):
		li = []
		for i in range(K):
			if arr[i] != None:
				a = node(-arr[i].data, arr[i])
				heapq.heappush(li, a)
		head = Node(-1)
		curr = head
		while li:
			popped = heapq.heappop(li)
			x = popped.value
			curr.next = x
			curr = curr.next
			if x.next != None:
				a = node(-x.next.data, x.next)
				heapq.heappush(li, a)
		return head.next


class Solution:

	def mergeKLists(self, arr, K):

		def merge2lists(l1, l2):
			curr = dummy = Node
			while l1 and l2:
				if l1.data > l2.data:
					dummy.next = l2
					l2 = l2.next
				else:
					dummy.next = l1
					l1 = l1.next
				dummy = dummy.next
			dummy.next = l2 if not l1 else l1
			return curr.next
		if not arr:
			return
		while len(arr) > 1:
			res = []
			for i in range(0, len(arr), 2):
				l1 = arr[i]
				l2 = arr[i + 1] if i + 1 < len(arr) else None
				res.append(merge2lists(l1, l2))
			arr = res
		return arr[0]


import heapq

class Solution:

	def mergeKLists(self, lists, K):
		heap = []
		for (i, lst) in enumerate(lists):
			if lst:
				heapq.heappush(heap, (lst.data, i, lst))
		dummy = Node(0)
		curr = dummy
		while heap:
			(val, i, node) = heapq.heappop(heap)
			curr.next = node
			curr = curr.next
			if node.next:
				heapq.heappush(heap, (node.next.data, i, node.next))
		return dummy.next


class Solution:

	def mergeList(self, head1, head2):
		(head, tail) = (None, None)
		while head1 and head2:
			if head == None:
				if head1.data < head2.data:
					head = head1
					tail = head1
					head1 = head1.next
				else:
					head = head2
					tail = head2
					head2 = head2.next
			elif head1.data < head2.data:
				tail.next = head1
				tail = tail.next
				head1 = head1.next
			else:
				tail.next = head2
				tail = tail.next
				head2 = head2.next
		if head1 != None:
			tail.next = head1
		if head2 != None:
			tail.next = head2
		return head

	def mergeKLists(self, lists, K):
		for l in lists:
			if l == None:
				lists.remove(l)
		k = len(lists)
		if k == 1:
			return lists[0]
		head = None
		for i in range(k - 1, 0, -1):
			lists[i - 1] = self.mergeList(lists[i], lists[i - 1])
		head = lists[0]
		return head


class Solution:

	def mergeKLists(self, arr, K):
		r = []
		for i in arr:
			t = i
			while t:
				r.append(t.data)
				t = t.next
		r.sort()
		a = b = Node(0)
		for i in r:
			a.next = Node(i)
			a = a.next
		return b.next


import heapq

class Solution:

	def mergeKLists(self, lists, K):
		heap = []
		for i in range(len(lists)):
			if lists[i]:
				heapq.heappush(heap, (lists[i].data, i))
		dummy = Node(float('inf'))
		curr = dummy
		while heap:
			(val, idx) = heapq.heappop(heap)
			curr.next = Node(val)
			curr = curr.next
			if lists[idx].next:
				lists[idx] = lists[idx].next
				heapq.heappush(heap, (lists[idx].data, idx))
		return dummy.next


class Solution:

	def mergeKLists(self, arr, K):
		res = []
		for I in arr:
			while I:
				res.append(I.data)
				I = I.next
		res.sort()
		curr = dummy = Node(0)
		for I in res:
			curr.next = Node(I)
			curr = curr.next
		return dummy.next


class Solution:

	def mergeKLists(self, arr, K):
		ans = []
		s = len(arr) - 1
		while s > -1:
			st = arr[s]
			while st:
				ans += [st.data]
				st = st.next
			s = s - 1
		st = None
		end = st
		i = 0
		ans.sort()
		while i != len(ans):
			if i == 0:
				st = Node(ans[i])
				end = st
			else:
				end.next = Node(ans[i])
				end = end.next
			i += 1
		return st


class Solution:

	def mergeKLists(self, arr, K):
		ans = []
		s = len(arr) - 1
		from heapq import heappush, heappop
		while s > -1:
			st = arr[s]
			while st:
				heappush(ans, st.data)
				st = st.next
			s = s - 1
		st = None
		end = st
		i = 0
		ans.sort()
		while len(ans) != 0:
			if i == 0:
				st = Node(heappop(ans))
				end = st
			else:
				end.next = Node(heappop(ans))
				end = end.next
			i += 1
		return st


import heapq

class Solution:

	def mergeKLists(self, arr, K):
		l = []
		for i in arr:
			while i:
				l.append(i.data)
				i = i.next
		heapq.heapify(l)
		head = Node(-1)
		tail = head
		while l:
			new = Node(heapq.heappop(l))
			tail.next = new
			tail = new
		return head.next


class Solution:

	def mergeKLists(self, arr, K):
		if len(arr) == 0:
			return None
		while len(arr) > 1:
			mergedL = []
			for i in range(0, len(arr), 2):
				l1 = arr[i]
				l2 = arr[i + 1] if i + 1 < len(arr) else None
				mergedL.append(self.mergeLists(l1, l2))
			arr = mergedL
		return arr[0]

	def mergeLists(self, l1, l2):
		head = Node(0)
		temp = head
		while l1 and l2:
			if l1.data < l2.data:
				temp.next = l1
				temp = l1
				l1 = l1.next
			else:
				temp.next = l2
				temp = l2
				l2 = l2.next
		if l1:
			temp.next = l1
		if l2:
			temp.next = l2
		return head.next