LeetCode #206 Reverse Linked List: พลิกพอยน์เตอร์ให้ชัวร์

โจทย์ให้หัวของ singly linked list แล้วคืนหัวของลิสต์ที่กลับลำดับแล้ว

วิธีที่ 1: วนซ้ำสามตัวชี้ (แนะนำหลัก)

เก็บ prev, curr, nxt แล้ววนพลิก curr.next = prev เวลา O(n) พื้นที่ O(1) Invariant หลังแต่ละรอบคือช่วงตั้งแต่หัวเดิมถึง prev ถูกพลิกแล้ว

วิธีที่ 2: รีเคอร์ซีฟ

พลิกส่วนหางก่อน แล้วตั้ง head.next.next = head และ head.next = None เวลา O(n) พื้นที่สแต็ก O(n) อ่านง่ายแต่เสี่ยงลึกในลิสต์ยาว

วิธีที่ 3: สแต็กช่วย

ดันโหนดลงสแต็กแล้วเอาออกทีละตัวต่อใหม่ เวลา O(n) พื้นที่ O(n) ชัดเจนแต่ใช่หน่วยความจำมากกว่าและมักไม่จำเป็น

import unittest


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


def to_list(head):
    out = []
    while head:
        out.append(head.val)
        head = head.next
    return out


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


def reverse_list_iterative(head):
    prev = None
    curr = head
    while curr:
        nxt = curr.next
        curr.next = prev
        prev = curr
        curr = nxt
    return prev


def reverse_list_recursive(head):
    if head is None or head.next is None:
        return head
    new_head = reverse_list_recursive(head.next)
    head.next.next = head
    head.next = None
    return new_head


class ReverseLinkedListTests(unittest.TestCase):
    def test_examples(self):
        cases = [
            ([1, 2, 3, 4, 5], [5, 4, 3, 2, 1]),
            ([1, 2], [2, 1]),
            ([], []),
            ([9], [9]),
        ]
        for values, expected in cases:
            with self.subTest(values=values):
                self.assertEqual(to_list(reverse_list_iterative(from_list(values))), expected)
                self.assertEqual(to_list(reverse_list_recursive(from_list(values))), expected)


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

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

สถานการณ์	วิธี
ค่าเริ่มต้น / ลิสต์ยาว	วนซ้ำ O(1) พื้นที่
สอนโครงสร้างรีเคอร์ซีฟ	รีเคอร์ซีฟ
ห้ามแก้พอยน์เตอร์เดิม (อิมมิวเทเบิลโหนด)	สร้างโหนดใหม่จากสแต็ก/อาร์เรย์
ต้องพลิกแค่ช่วงย่อย	ปรับสามตัวชี้ให้มีขอบซ้าย-ขวา

Recap

• จำสามตัวชี้ prev/curr/nxt ให้ขึ้นใจ
• ทดสอบลิสต์ว่าง โหนดเดียว และสองโหนด
• รีเคอร์ซีฟสวยแต่กินสแต็ก
• อย่าทำหายหัวเดิมก่อนเก็บ nxt