Linked List — จากศูนย์จนพร้อมลุย LeetCode

หลายคนกลัว Linked List เพราะมันมองไม่เห็นภาพเหมือนการเก็บข้อมูลแบบ List ธรรมดา แต่เชื่อไหมครับว่า ถ้าคุณเข้าใจคอนเซปต์ของมัน มันจะกลายเป็นเรื่องที่สนุกและพลิกแพลงได้เยอะมาก — เรามาค่อย ๆ แกะกันทีละสเต็ป จากศูนย์จนพร้อมลุย LeetCode ครับ!

ข้อแตกต่างสำคัญที่ต้องจำไว้ก่อน: Linked List ใช้ Index (arr[i]) ไม่ได้ เพราะโหนดกระจัดกระจายอยู่ในหน่วยความจำ การจะแก้โจทย์ให้ผ่าน 100% จึงขึ้นอยู่กับการควบคุม "ข้อต่อ (Pointers)" เท่านั้น

1. ปลดล็อกไอเดีย: ทิ้งโรงหนัง แล้วไปสร้างขบวนรถไฟ

ปกติเวลาเราเก็บข้อมูลใน Python List (เช่น [10, 20, 30]) ข้อมูลจะถูกวางเรียงติดกันเป็นแถวยาว ๆ เหมือน "ที่นั่งในโรงหนัง"

• ข้อดี: ถ้าอยากเรียกคนนั่งเก้าอี้เบอร์ 5 ก็ชี้ตัวได้ทันที
• ข้อเสีย: ถ้ามีคนอยากมาแทรกตรงกลาง คุณต้องสั่งให้คนที่นั่งอยู่ "ขยับถอยไปทีละเก้าอี้" ทั้งแถว! วุ่นวายสุด ๆ

ภาพจำใหม่ของ Linked List: ให้คุณเปลี่ยนมุมมองใหม่ นึกถึง "ขบวนรถไฟ" ครับ! ตู้รถไฟแต่ละตู้จอดอยู่คนละที่กันในลานกว้าง ๆ ไม่ได้อยู่ติดกัน สิ่งที่ทำให้มันเชื่อมกันได้คือ "ข้อต่อ (โซ่)" ที่เกี่ยวตู้แรกไปหาตู้ที่สอง ตู้สองไปหาตู้สาม... ไปเรื่อย ๆ

2. โครงสร้างของ "ตู้รถไฟ" (The Node)

ตู้รถไฟ 1 ตู้ (เราเรียกศัพท์เทคนิคว่า Node หรือ โหนด) จะมีส่วนประกอบสำคัญแค่ 2 อย่างเท่านั้นครับ:

1. val (Value) — กล่องบรรจุสัมภาระ (เก็บตัวเลข, ข้อความ หรืออะไรก็ได้)
2. next (Pointer) — ข้อต่อโซ่ที่ชี้บอกทางว่า "ตู้ถัดไปอยู่ที่ไหน?"

และมีตัวแปรพิเศษอีก 2 ตัวที่ต้องจำให้ขึ้นใจ:

• Head (หัวขบวน) — ตู้แรกสุดของขบวน (ถ้ารักษา Head ไว้ไม่ได้ คุณจะหาตู้ที่เหลือไม่เจออีกเลย!)
• None (จบขบวน) — ตู้สุดท้ายจะต้องชี้ข้อต่อ next ไปหาความว่างเปล่า เพื่อบอกว่าสิ้นสุดขบวนแล้ว

3. [Workshop] ลองสร้างรถไฟแบบจับมือทำ (Absolute Zero)

เรามาสวมบทเป็นวิศวกรสร้างรถไฟ 2 ตู้ใน Python กันดูครับ ลืมอัลกอริทึมซับซ้อนไปก่อนเลย!

ขั้นที่ 1: สร้างโรงงานผลิตตู้รถไฟ (พิมพ์เขียว) — คอมพิวเตอร์ไม่รู้จักตู้รถไฟ เราต้องสร้าง Class ขึ้นมาสอนมันก่อน:

class ListNode:
    def __init__(self, value=0, next=None):
        self.val = value     # เก็บของลงกล่อง
        self.next = next     # โซ่ชี้ไปตู้ถัดไป (ตอนเพิ่งสร้างเสร็จยังไม่เกี่ยวใคร = None)

ขั้นที่ 2: ผลิตตู้รถไฟออกมา 2 ตู้ — สั่งผลิตตู้แรกใส่เลข 10 ตู้สองใส่เลข 20 (ตอนนี้รถไฟยังจอดแยกกันอยู่ ไม่มีใครรู้จักใคร)

nodeA = ListNode(10)
nodeB = ListNode(20)

ขั้นที่ 3: เอาโซ่คล้องตู้เข้าด้วยกัน! — ไฮไลต์อยู่ตรงนี้ครับ เราจะเอาโซ่ของตู้ A (nodeA.next) ไปเกี่ยวเข้ากับตู้ B (nodeB)

nodeA.next = nodeB
# เย้! ตอนนี้มันกลายเป็น Linked List แล้ว: [10] -> [20] -> None

ขั้นที่ 4: ลองพิสูจน์ดูสิว่ามันเชื่อมกันจริงไหม?

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

nodeA = ListNode(10)
nodeB = ListNode(20)
nodeA.next = nodeB

print(nodeA.val)          # ของในตู้ A
print(nodeA.next.val)     # ยืนอยู่ตู้ A -> เดินตามโซ่ไปตู้ถัดไป -> เปิดกล่องดูของ

10
20

4. ท่ามาตรฐาน: วิธีเดินตรวจขบวนรถไฟ (Traversal)

ใน LeetCode คุณจะไม่ได้มีรถไฟแค่ 2 ตู้ แต่มาเป็นสิบเป็นร้อยตู้ ท่ามาตรฐานที่คุณต้องพิมพ์ให้ชินมือคือ การใช้ while loop เดินตรวจรถไฟตั้งแต่หัวยันท้ายขบวน ครับ

สมมติเรามีขบวน head = [10] -> [20] -> [30]

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

# สร้างขบวน [10] -> [20] -> [30]
head = ListNode(10)
head.next = ListNode(20)
head.next.next = ListNode(30)

curr = head           # 1. ตั้งชื่อตัวแทนเดินตรวจว่า curr เริ่มยืนที่หัวขบวน

while curr:           # 2. ตราบใดที่ curr ยังยืนอยู่บนตู้ (ยังไม่ตกขบวนไปเจอ None)
    print(curr.val)   # 3. ดูว่าตู้ที่ยืนอยู่มีของอะไร
    curr = curr.next  # 4. เดินก้าวไปตู้ถัดไปตามโซ่! (ขาดบรรทัดนี้ลูปจะค้าง)

10
20
30

5. สัญญาณเตือนว่าโจทย์ข้อนี้ "เล่นกับ Linked List"

เวลาทำ LeetCode ถ้าฟังก์ชันรับค่าตัวแปรประเภท ListNode เข้ามา เตรียมงัดแพทเทิร์นยอดฮิตเหล่านี้มาใช้ได้เลย:

• การเดิน 2 จังหวะ (Fast & Slow Pointers) — ให้คนนึงเดินทีละก้าว อีกคนวิ่งทีละ 2 ก้าว เอาไว้หา "จุดกึ่งกลางขบวน" หรือจับผิดว่า "รถไฟวิ่งวนเป็นวงกลมไหม"
• การสลับสาย (Reverse) — สั่งให้หันข้อต่อโซ่กลับหลังหันทั้งขบวน (เช่น จาก 1→2→3 เปลี่ยนเป็น 3→2→1)
• การเย็บผ้า (Merge) — เอาขบวนรถไฟ 2 ขบวนมารูดซิปสลับตู้กันให้กลายเป็นขบวนเดียว

พื้นฐานแน่นแล้ว! ต่อไปคือ 5 เทคนิคที่โจทย์ Linked List ใน LeetCode เกือบ 90% ใช้ผสมผสานกัน — อ่านต่อให้จบ แล้วพร้อมลุยได้เลยครับ

6. 5 เทคนิคระดับเทวดา (Must-Know Patterns for LeetCode)

Pattern 1: Dummy Head (โหนดหลอกแก้ Edge Case)

• ปัญหา: เวลาโจทย์ให้ ลบ, สลับ, หรือ เพิ่ม โหนดที่ตำแหน่งแรกสุด (Head) คำตอบของ Head จะเปลี่ยนไป ทำให้เราต้องเขียน if-else เช็คกรณีหัวขบวนซับซ้อนมาก
• วิธีแก้: สร้างโหนดหลอกขึ้นมา 1 ตัว แปะไว้หน้า Head เสมอ แล้วส่งคืน dummy.next เป็นคำตอบตอนจบ

dummy = ListNode(0)   # สร้างโหนดหลอก ค่าอะไรก็ได้
dummy.next = head     # เอาโหนดหลอกต่อเข้ากับ Head เดิม
curr = dummy          # ใช้ curr เดินทำงาน

# ... จัดการเปลี่ยนข้อต่อต่างๆ ...

return dummy.next     # คำตอบที่แท้จริงคือตัวที่อยู่หลัง Dummy

Pattern 2: Fast & Slow Pointers (สองเข็มความเร็วต่างกัน)

เทคนิคนี้ใช้กระต่าย (Fast) วิ่งเร็วกว่าเต่า (Slow) 2 เท่า เอาไว้แก้โจทย์ 2 สไตล์หลัก:

1. หาจุดกึ่งกลางของ List — slow เดินทีละ 1 ก้าว (slow = slow.next) · fast เดินทีละ 2 ก้าว (fast = fast.next.next) · เมื่อ fast ถึงปลายทาง slow จะยืนอยู่ตรงจุดกึ่งกลางพอดีเป๊ะ!
2. เช็คว่ามีวงวน (Cycle) หรือไม่ — ถ้าวิ่งไปเรื่อย ๆ แล้ว fast == slow แปลว่าวิ่งวนกลับมาชนกัน มี Cycle แน่นอน (Floyd's Cycle Finding Algorithm)

slow = fast = head
while fast and fast.next:
    slow = slow.next          # เดิน 1 ก้าว
    fast = fast.next.next     # เดิน 2 ก้าว

Pattern 3: In-Place Reversal (การกลับทิศลิงก์ลิสต์)

การเปลี่ยนทิศทางจาก 1 → 2 → 3 ให้กลายเป็น 3 → 2 → 1 โดยไม่สร้างโหนดใหม่ — ใช้ตัวแปร 3 ตัวควบคุมการหมุนข้อต่อ:

• prev — โหนดก่อนหน้า (เริ่มต้นเป็น None)
• curr — โหนดปัจจุบันที่กำลังตัดข้อต่อ (เริ่มต้นเป็น head)
• nxt — โหนดถัดไป (เอาไว้เซฟทางไปต่อ ไม่ให้หลุดขบวน)

prev = None
curr = head

while curr:
    nxt = curr.next   # 1. จำทางไปต่อไว้ก่อน
    curr.next = prev  # 2. หักข้อต่อกลับหลังชี้หา prev
    prev = curr       # 3. เขยิบ prev ตามมา
    curr = nxt        # 4. เขยิบ curr ไปโหนดถัดไป

return prev           # prev จะกลายเป็น Head ตัวใหม่

Pattern 4: Pointer Cutting & Re-linking (การตัด-ต่อข้อต่อ)

เวลาต้องการลบโหนด B ออกจากขบวน A → B → C — เราไม่ต้องลบ B ทิ้งจริง ๆ ในหน่วยความจำ แค่สั่งให้ A ข้ามไปชี้ C แทน:

A.next = A.next.next

Pattern 5: Boundary Check (การตั้งเงื่อนไขลูปไม่ให้โค้ดพัง)

ก่อนจะขยับ Pointer ต้องตั้งเงื่อนไข while ให้ครอบคลุมเสมอ:

7. ตะลุยโจทย์จริง: LC206 — Reverse Linked List

ลองเอา Pattern 3 (In-Place Reversal) มาเขียนใส่ฟังก์ชันจริงส่ง LeetCode:

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        prev = None
        curr = head

        while curr:
            nxt = curr.next   # เซฟโหนดถัดไป
            curr.next = prev  # กลับทิศชี้หาตัวหน้า
            prev = curr       # เลื่อน prev
            curr = nxt        # เลื่อน curr

        return prev  # คืนค่าหัวขบวนใหม่

จำลองขั้นตอนการทำงาน (Walkthrough)

สมมติ input คือ 1 → 2 → 3 → None

สัญลักษณ์ | แยกสองชิ้น: ซ้าย = ส่วนที่พลิกแล้ว · ขวา = ส่วนที่ยังไม่แตะ พอลูปจบ curr เป็น None แล้วคืน prev (= โหนด 3) เป็น Head ใหม่ ได้ 3 → 2 → 1 — O(N) Time / O(1) Space!

8. Checklist เช็คโค้ดก่อนกด Submit

ก่อนกดปุ่ม Submit ใน LeetCode ให้เช็ค 4 ข้อนี้เสมอ:

1. Empty List — ถ้า head == None โค้ดพังไหม?
2. Single Node — ถ้า List มีโหนดเดียว (head.next == None) โค้ดทำงานถูกต้องไหม?
3. Two Nodes — ถ้า List มีแค่ 2 โหนด วนลูปหลุดไหม?
4. Cycle Hazard — มีตรงไหนเขียนชี้กลับหาตัวเองจนเกิด Infinite Loop หรือเปล่า?