LeetCode #21 Merge Two Sorted Lists: เลือกโหนดเล็กแล้วต่อหาง

โจทย์ให้หัวของ singly linked list สองเส้นซึ่งเรียงจากน้อยไปมาก แล้วคืนลิสต์เรียงเส้นเดียวครับ หัวใจไม่ใช่ sort ใหม่ แต่คือเทียบหัวที่ยังเหลือ เลือกค่าต่ำกว่าไปต่อหาง แล้วขยับเฉพาะลิสต์นั้น

วิธีที่ 1: Iterative พร้อม dummy node — ค่าเริ่มต้นที่แนะนำ

สร้าง dummy เป็นหลักยึดหาง จากนั้นวนขณะทั้งสองลิสต์ยังมีโหนด เลือกโหนดเล็กกว่าแล้วต่อเข้าหาง เมื่อเส้นหนึ่งหมด ให้ต่อส่วนที่เหลืออีกเส้นได้ทันที เพราะมันเรียงอยู่แล้ว เวลา O(n+m), หน่วยความจำเพิ่ม O(1) และ reuse โหนดเดิม

วิธีที่ 2: Recursion

เลือกหัวที่เล็กกว่า แล้วให้ next ของหัวนั้นเป็นผล merge ของส่วนที่เหลือ เวลา O(n+m), call stack O(n+m) โค้ดสั้นแต่เสี่ยง recursion limit เมื่อ input ยาว และแก้ pointer เดิมเช่นเดียวกับวิธีแรก

วิธีที่ 3: สร้างโหนดใหม่

เดินสองลิสต์เหมือน iterative แต่ copy ค่าเข้า node ใหม่ เวลา O(n+m), พื้นที่ O(n+m) เหมาะเมื่อ caller ยังต้องใช้โครงสร้างเดิมและ ownership ห้าม mutation ข้อเสียคือ allocation เพิ่มและ identity ของโหนดหาย

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):
    values = []
    while node:
        values.append(node.val)
        node = node.next
    return values


def merge_iterative(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_recursive(a, b):
    if not a or not b:
        return a or b
    if a.val <= b.val:
        a.next = merge_recursive(a.next, b)
        return a
    b.next = merge_recursive(a, b.next)
    return b


def merge_copy(a, b):
    dummy = tail = ListNode()
    while a or b:
        if b is None or (a is not None and a.val <= b.val):
            value, a = a.val, a.next
        else:
            value, b = b.val, b.next
        tail.next = ListNode(value)
        tail = tail.next
    return dummy.next


class MergeListsTests(unittest.TestCase):
    def test_methods_and_edges(self):
        cases = [([], [], []), ([], [1], [1]), ([1, 2, 4], [1, 3, 4], [1, 1, 2, 3, 4, 4])]
        for left, right, expected in cases:
            for method in (merge_iterative, merge_recursive, merge_copy):
                with self.subTest(method=method.__name__, left=left, right=right):
                    self.assertEqual(to_list(method(from_list(left), from_list(right))), expected)


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

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

เงื่อนไข	Iterative reuse	Recursion	Copy ใหม่
input ใหญ่	ดีที่สุด	เสี่ยง stack	ใช้ได้แต่ allocation สูง
memory จำกัด	O(1) เพิ่ม	O(n+m) stack	O(n+m) heap
readability	ชัดเมื่อใช้ dummy	สั้นที่สุด	ชัดเรื่อง ownership
input sorted/streaming	ต้อง sorted; ต่อ remainder ได้	ต้อง sorted; ไม่เหมาะ stream ยาว	ต้อง sorted; ปรับเป็น iterator ได้
อนุญาตแก้ input	ใช่	ใช่	ไม่จำเป็น

best default ภายใต้ constraints ของโจทย์คือ iterative reuse เพราะเวลาเส้นตรงและพื้นที่เพิ่มคงที่

Edge cases

ทดสอบลิสต์ว่างหนึ่งหรือสองเส้น, ค่าซ้ำ, ค่าติดลบ และเส้นที่ค่าทั้งหมดเล็กกว่าอีกเส้น ใช้ <= เพื่อให้โหนดจากซ้ายมาก่อนเมื่อค่าเท่ากัน ซึ่งทำให้ merge มีเสถียรภาพหาก identity สำคัญ

Recap

• รักษา invariant ว่าช่วงหลัง dummy เรียงแล้ว
• ต่อ remainder ทั้งก้อนได้เมื่ออีกเส้นหมด
• iterative reuse เป็น default ที่สมดุลที่สุด
• copy ใหม่เมื่อห้ามแตะ input เดิม