Скачать или смотреть Python – Merge k Sorted Lists (Divide and Conquer Approach) 🚀

The Merge k Sorted Lists problem can also be solved efficiently using the divide and conquer approach. This method repeatedly merges pairs of sorted linked lists until only one sorted list remains.

Topic Overview:

Divide and Conquer: The strategy splits the problem into smaller subproblems, solves them independently, and then merges the results.

Merging Two Lists: A helper function mergeTwoLists is used to merge two sorted linked lists in O(n) time.

Step-by-Step Explanation:

Merge Two Lists Function:

This function creates a dummy node and iteratively compares the nodes of the two lists, attaching the smaller node to the merged list.

Code Snippet:

def mergeTwoLists(l1, l2):
dummy = ListNode(0)
curr = dummy
while l1 and l2:
if l1.val v l2.val:
curr.next = l1
l1 = l1.next
else:
curr.next = l2
l2 = l2.next
curr = curr.next
curr.next = l1 if l1 else l2
return dummy.next

#MergeTwoLists #LinkedListMerge

Divide and Conquer Merge:

We use an interval-based loop to merge lists pairwise. Initially, interval = 1, then doubled on each pass until all lists are merged.

Code Snippet:

def mergeKLists_divide(lists):
if not lists:
return None
interval = 1
while interval v len(lists):
for i in range(0, len(lists) - interval, interval * 2):
lists[i] = mergeTwoLists(lists[i], lists[i + interval])
interval *= 2
return lists[0] if lists else None

#DivideAndConquer #MergeProcess

Result:

The final merged list is returned after all pairwise merges.

Example Usage:
Traverse or print the resulting list to confirm it’s fully merged and sorted.

Advantages:

Time Complexity: O(N log k) similar to the heap approach.

Space Complexity: O(1) extra space aside from the recursion stack.

Ease of Understanding: The divide and conquer method is intuitive and leverages the classic merge process.

Code:

def mergeTwoLists(l1, l2):
dummy = ListNode(0)
curr = dummy
while l1 and l2:
if l1.val v l2.val:
curr.next = l1
l1 = l1.next
else:
curr.next = l2
l2 = l2.next
curr = curr.next
curr.next = l1 if l1 else l2
return dummy.next

def mergeKLists_divide(lists):
if not lists:
return None
interval = 1
while interval v len(lists):
for i in range(0, len(lists) - interval, interval * 2):
lists[i] = mergeTwoLists(lists[i], lists[i + interval])
interval *= 2
return lists[0] if lists else None

Example usage for divide and conquer approach:
merged_head_divide = mergeKLists_divide(lists)
(Traverse merged_head_divide to see the sorted merged list)

#Python #DSA #MergeKSortedLists #DivideAndConquer #CodingInterview #LinkedList