บทเรียน: Linked List
👋 อ่านฟรีทั้งหมดบน Aph's Blog — เนื้อหาภาษาไทย ทำตามทีละหน้าใน sidebar ได้เลย หากมีข้อเสนอแนะหรืออยากให้เพิ่มหัวข้อไหน บอกได้เสมอ
ข้อมูลที่แต่ละ node ชี้ไปยัง node ถัดไป — ฝึก reverse, หา cycle และ merge
Linked list คือชุด node ที่แต่ละตัวเก็บค่าและ pointer ชี้ไป node ถัดไป ต่างจาก array ตรงที่ไม่ต้องเก็บต่อเนื่องในหน่วยความจำ เพิ่ม/ลบหัวท้ายเร็ว (O(1)) แต่เข้าถึงตำแหน่งกลางช้า (O(n))
โครงสร้าง node
python
class Node:
def __init__(self, val):
self.val = val
self.next = NoneReverse a Linked List (เจอบ่อยมาก)
python
def reverse(head):
prev = None
cur = head
while cur:
nxt = cur.next # จำตัวถัดไปไว้
cur.next = prev # กลับทิศ
prev = cur
cur = nxt
return prev # หัวใหม่หา Cycle ด้วย Fast & Slow Pointer
python
def has_cycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next # เดินทีละ 1
fast = fast.next.next # เดินทีละ 2
if slow is fast:
return True # เจอกัน = มี cycle
return Falseข้อควรระวัง
ระวัง null pointer (เช็ค node ก่อนใช้ .next) และระวังทำ list ขาดตอนแก้ pointer — เขียน step ทีละขั้นบนกระดาษช่วยได้มาก