Merge k Sorted Lists
- 1 min read
- Heap
- LC-Hard
- Blind75
- Merge Sort
- Linked List
- Divide and Conquer
3 years ago
Approach 1: Brute Force
Iterate through each list, add valeus to list, sort list, and create a new linked list.
def mergeKLists(lists: List[Optional[ListNode]]) -> Optional[ListNode]:
values = []
for list_head in lists:
cur = list_head
while cur:
values.append(cur.val)
cur = cur.next
values.sort()
head = dummy = ListNode()
for value in values:
head.next = ListNode(value)
head = head.next
return dummy.next
Approach 2: Merge Two Lists
- Merge two lists at a time, add new list back to array
- Repeat until array has only one list
def mergeKLists(lists: List[Optional[ListNode]]) -> Optional[ListNode]:
if len(lists) == 0: return None
while len(lists) > 1:
merged_lists = []
for i in range(0, len(lists), 2):
l1 = lists[i]
l2 = lists[i + 1] if i + 1 < len(lists) else None
merged_lists.append(self.merge_two_lists(l1, l2))
lists = merged_lists
return lists[0]
def merge_two_lists(self, l1, l2):
dummy = l3 = ListNode()
while l1 and l2:
if l1.val < l2.val:
l3.next = ListNode(l1.val)
l1 = l1.next
else:
l3.next = ListNode(l2.val)
l2 = l2.next
l3 = l3.next
if l1: l3.next = l1
if l2: l3.next = l2
return dummy.next