LeetCode #23 Merge k Sorted Lists: เลือกหัวที่เล็กสุดโดยไม่ sort ทั้งกอง

เรามี linked list เรียงจากน้อยไปมาก k เส้น และต้องรวมเป็นเส้นเดียวครับ ถ้ามีโหนดทั้งหมด N การ sort ค่าทั้งหมดทำได้ แต่ทิ้งข้อมูลสำคัญว่าแต่ละเส้นเรียงแล้ว วิธีที่ดีกว่าคือเทียบเฉพาะ “หัวคิว” ที่พร้อมถูกเลือก

เหมือนมีสายพาน k เส้นที่แต่ละเส้นจัดของเล็กไปใหญ่ เราไม่ต้องเทของทั้งหมดลงพื้น แค่ดูของชิ้นหน้าสุด เลือกชิ้นเล็กสุด แล้วเลื่อนสายพานเส้นนั้นหนึ่งครั้ง

วิธีที่ 1: รวมค่าแล้ว sort

เดินทุกโหนด เก็บค่าใน array, sort แล้วสร้าง list ใหม่ เวลา O(N log N), พื้นที่ O(N) เข้าใจง่ายและไม่แก้ input แต่ไม่ใช้ประโยชน์จากลำดับเดิม และ identity ของ node หาย เหมาะเป็น baseline สำหรับทดสอบมากกว่าวิธี production

วิธีที่ 2: Merge ทีละเส้น

เริ่ม result ว่างแล้ว merge กับ list ถัดไปด้วยอัลกอริทึมสองลิสต์ หากเส้นแรก ๆ ยาวขึ้นเรื่อย ๆ โหนดเดิมจะถูกเดินซ้ำ เวลาร้ายสุด O(Nk), พื้นที่เพิ่ม O(1) และ reuse node ได้ โค้ดสั้น แต่ช้าชัดเมื่อ k มากและความยาวกระจายใกล้กัน

วิธีที่ 3: Min-heap — ค่าเริ่มต้นที่แนะนำ

ใส่หัวของแต่ละลิสต์ลง heap ขนาดไม่เกิน k ทุกครั้งดึงค่าน้อยสุดมาต่อผลลัพธ์ แล้วใส่ next ของเส้นนั้นกลับเข้า heap เวลา O(N log k), พื้นที่ O(k) ใช้ tuple (value, serial, node) เพื่อให้ค่าซ้ำไม่บังคับ Python เปรียบเทียบ object

วิธีที่ 4: Divide and conquer

จับคู่ merge ลิสต์เป็นรอบ ๆ คล้าย tournament จำนวนรอบ O(log k) และแต่ละรอบเดินรวม O(N) จึงได้ O(N log k), พื้นที่เพิ่ม O(1) นอก call/loop bookkeeping เหมาะเมื่อข้อมูลอยู่ใน memory และต้องการ locality ดีกว่า heap

import heapq
import itertools
import unittest


class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


def from_list(values):
    dummy = tail = ListNode()
    for value in values:
        tail.next = ListNode(value)
        tail = tail.next
    return dummy.next


def to_list(node):
    result = []
    while node:
        result.append(node.val)
        node = node.next
    return result


def merge_two(a, b):
    dummy = tail = ListNode()
    while a and b:
        if a.val <= b.val:
            tail.next, a = a, a.next
        else:
            tail.next, b = b, b.next
        tail = tail.next
    tail.next = a or b
    return dummy.next


def merge_sequential(lists):
    result = None
    for node in lists:
        result = merge_two(result, node)
    return result


def merge_heap(lists):
    counter = itertools.count()
    heap = []
    for node in lists:
        if node:
            heapq.heappush(heap, (node.val, next(counter), node))
    dummy = tail = ListNode()
    while heap:
        _, _, node = heapq.heappop(heap)
        tail.next = node
        tail = node
        if node.next:
            heapq.heappush(heap, (node.next.val, next(counter), node.next))
    return dummy.next


def merge_divide(lists):
    work = list(lists)
    interval = 1
    while interval < len(work):
        for index in range(0, len(work) - interval, interval * 2):
            work[index] = merge_two(work[index], work[index + interval])
        interval *= 2
    return work[0] if work else None


class MergeKTests(unittest.TestCase):
    def test_methods_and_edges(self):
        cases = [([], []), ([[]], []), ([[1, 4, 5], [1, 3, 4], [2, 6]], [1, 1, 2, 3, 4, 4, 5, 6])]
        for groups, expected in cases:
            for method in (merge_sequential, merge_heap, merge_divide):
                with self.subTest(method=method.__name__, groups=groups):
                    lists = [from_list(values) for values in groups]
                    self.assertEqual(to_list(method(lists)), expected)


if __name__ == "__main__":
    unittest.main()

เลือกตามสถานการณ์

เงื่อนไข	Collect + sort	ทีละเส้น	Heap	Divide & conquer
input ใหญ่ / k มาก	O(N log N)	อาจ O(Nk)	O(N log k)	O(N log k)
memory จำกัด	O(N)	O(1) เพิ่ม	O(k)	O(1) เพิ่มโดยประมาณ
readability	ง่ายสุด	ง่าย	ต้องเข้าใจ heap	ต้องเข้าใจรอบจับคู่
sorted/streaming input	ไม่ใช้ลำดับ	ต้องมี node chain	ใช้ได้ดีและดึงทีละ node	ต้องถือหัวทุก list
อนุญาตแก้ input	ไม่จำเป็น	reuse node	reuse node	reuse node

best default ภายใต้ constraints ของโจทย์คือ min-heap เพราะรักษา O(N log k), อ่านข้อมูลทีละหัว และรับ list ว่างหรือความยาวไม่สมดุลได้ตรงไปตรงมา ถ้า memory เข้มมากและข้อมูลอยู่ครบในเครื่อง divide-and-conquer เป็นคู่แข่งที่ดี

Edge cases

ทดสอบ lists=[], มีแต่ list ว่าง, ค่าซ้ำ, ค่าติดลบ และ k=1 อย่าดัน None เข้า heap และต้องมี serial tie-breaker เมื่อค่าเท่ากัน มิฉะนั้น Python จะพยายามเปรียบเทียบ ListNode

Recap

• ใช้ความจริงที่แต่ละ list เรียงแล้วโดยเทียบเฉพาะหัว
• heap จำกัดผู้สมัครไว้ไม่เกิน k โหนด
• divide-and-conquer ได้ complexity เดียวกันโดยไม่ใช้ heap
• collect-sort เหมาะเป็น baseline แต่ไม่ใช่ default