Merge multiple sorted lists, sort a list, or partition around a value
Use dummy heads and pointer weaving; for k-way merges use a heap; for sort use merge sort on list.
Use for merging k sorted lists, sorting a list in O(n log n), or partitioning relative to a pivot.
K-way merge with a min-heap and stable partitioning via two dummy-headed chains; list merge-sort fits the same pointer-weaving pattern.
# Merge/Split Templates
import heapq
def merge_k_lists(lists):
heap=[]
for i,node in enumerate(lists):
if node: heapq.heappush(heap,(node.val,i,node))
dummy=ListNode(0); cur=dummy
while heap:
_,i,n = heapq.heappop(heap)
cur.next=n; cur=cur.next
if n.next: heapq.heappush(heap,(n.next.val,i,n.next))
return dummy.next
def partition_list(head, x):
small = s_tail = ListNode(0)
large = l_tail = ListNode(0)
cur=head
while cur:
nxt=cur.next; cur.next=None
if cur.val < x: s_tail.next=cur; s_tail=cur
else: l_tail.next=cur; l_tail=cur
cur=nxt
s_tail.next=large.next
return small.nextMin-heap of list heads or divide & conquer
import heapq
def merge_k_lists(lists):
heap = []
for i, node in enumerate(lists):
if node: heapq.heappush(heap, (node.val, i, node))
dummy = ListNode(0)
cur = dummy
while heap:
_, i, node = heapq.heappop(heap)
cur.next = node; cur = cur.next
if node.next:
heapq.heappush(heap, (node.next.val, i, node.next))
return dummy.nextTop-down or bottom-up merge sort on list
def sort_list(head):
if not head or not head.next: return head
# split
slow, fast = head, head.next
while fast and fast.next: slow = slow.next; fast = fast.next.next
mid = slow.next; slow.next = None
# merge
left = sort_list(head); right = sort_list(mid)
return merge(left, right)
def merge(a, b):
dummy = ListNode(0); cur = dummy
while a and b:
if a.val < b.val: cur.next, a = a, a.next
else: cur.next, b = b, b.next
cur = cur.next
cur.next = a or b
return dummy.nextStable partition using two chains
def partition_list(head, x):
before = ListNode(0); after = ListNode(0)
b, a = before, after
cur = head
while cur:
if cur.val < x:
b.next = cur; b = b.next
else:
a.next = cur; a = a.next
cur = cur.next
a.next = None; b.next = after.next
return before.nextHeap/divide & conquer costs.
Pointers; recursion costs log n.