Linked List

ภาพรวม Pattern ที่พบบ่อยใน Linked List

หลังจากเรียนรู้พื้นฐานและการดำเนินการต่าง ๆ แล้ว — มาต่อด้วย pattern ที่พบบ่อยในโจทย์ linked list: Reverse (กลับทิศ), Middle Node (หาจุดกึ่งกลาง), Cycle Detection (ตรวจจับวงวน), และ Slow/Fast Pointer Technique — pattern เหล่านี้เป็นเครื่องมือสำคัญที่ใช้แก้ปัญหาได้หลากหลาย

• **Reverse** — กลับทิศ next pointer ทุกตัวใน list → ใช้ 3 ตัวแปร (prev, current, next)
• **Middle Node** — หาโหนดตรงกลางโดยไม่ต้องนับขนาดก่อน → ใช้ slow/fast pointers
• **Cycle Detection** — ตรวจจับวงวน (cycle) ใน linked list → Floyd's Tortoise & Hare algorithm
• **Slow/Fast Pointers** — เทคนิคใช้สอง pointer ที่ความเร็วต่างกันเพื่อหา pattern ในโครงสร้าง

Reverse Linked List — กลับทิศ list ทั้งหมด

การ reverse linked list คือการกลับทิศ next pointer ของทุก node — จาก A→B→C กลายเป็น C→B→A — เป็น operation พื้นฐานที่ใช้บ่อยมากในการแก้ปัญหา

• **Step 1:** เตรียม 3 ตัวแปร: `prev = null`, `current = head`, `nextNode` (ใช้ในลูป)
• **Step 2:** ในลูปแต่ละรอบ: เก็บ `nextNode = current.next` ก่อน (กัน reference หาย)
• **Step 3:** กลับทิศ: `current.next = prev` — เหลือแค่ prev ← current
• **Step 4:** เลื่อนตัวแปร: `prev = current`, `current = nextNode` — ขยับไป node ถัดไป
• **Step 5:** จบเมื่อ `current === null` — `prev` กลายเป็น head ใหม่

function reverse(head) {
  let prev = null;
  let current = head;

  while (current !== null) {
    const nextNode = current.next; // เก็บ next ไว้ก่อน
    current.next = prev;           // กลับทิศ next ให้ชี้กลับไป prev
    prev = current;                // ขยับ prev ไป current
    current = nextNode;            // ขยับ current ไป next ที่เก็บไว้
  }

  return prev; // prev คือ head ใหม่
}

const head = makeList([10, 20, 30]);
const reversed = reverse(head);
// reversed: 30 → 20 → 10

Reverse linked list ทำงานใน O(n) และใช้พื้นที่เพิ่ม O(1) — เพราะเราใช้แค่ 3 ตัวแปร (prev, current, nextNode) โดยไม่ต้องสร้างโครงสร้างข้อมูลใหม่

ดูโค้ดทำงานทีละขั้น — Reverse Linked List

หา Middle Node ด้วย Slow/Fast Pointers

การหา node ตรงกลางของ linked list สามารถทำได้โดยการเดินนับขนาดก่อน (2 pass: pass 1 นับ n, pass 2 เดินไป n/2) — แต่วิธีที่ elegant กว่าคือใช้ **slow/fast pointers**: slow เดินทีละ 1 ก้าว, fast เดินทีละ 2 ก้าว — เมื่อ fast ถึงปลายทาง slow จะอยู่ตรงกลางพอดี

function findMiddle(head) {
  let slow = head;
  let fast = head;

  while (fast !== null && fast.next !== null) {
    slow = slow.next;      // เต่าคลานทีละ 1
    fast = fast.next.next; // กระต่ายกระโดดทีละ 2
  }

  return slow; // เต่าอยู่ตรงกลาง
}

// Example
const head = makeList([10, 20, 30, 40, 50]);
console.log(findMiddle(head).value); // 30

const head2 = makeList([10, 20, 30, 40]);
console.log(findMiddle(head2).value); // 30 (ตัวที่สองของครึ่งแรก)

Slow (เต่า) & Fast (กระต่าย): เมื่อกระต่ายถึงเส้นชัย เต่าจะอยู่กลางทาง

เทคนิคนี้ใช้ได้เพราะ: ถ้า fast เดิน 2 เท่าของ slow — เมื่อ fast ถึงปลายทาง (null) slow จะเดินได้ครึ่งทางพอดี — ใช้เวลา O(n) เดินครั้งเดียว ไม่ต้องนับขนาดก่อน ^: หมายเหตุ: ถ้า linked list มีจำนวน node เป็นเลขคู่ middle จะตกที่ node ที่ n/2 (ตัวที่สองของครึ่งซ้าย) — เพราะ condition `fast.next !== null` จะทำให้ลูปหยุดเมื่อ fast อยู่ที่ node ก่อนสุดท้าย

Cycle Detection — ตรวจจับวงวนใน Linked List

Cycle (วงวน) ใน linked list เกิดขึ้นเมื่อ next pointer ของ node บางตัวชี้กลับไปยัง node ก่อนหน้า ทำให้ traverse แล้วไม่มีวันจบ — การตรวจจับ cycle ใช้ **Floyd's Cycle Detection** (Tortoise & Hare): ถ้า slow กับ fast เดินด้วยความเร็วต่างกันแล้วมาเจอกันในลูป แปลว่ามี cycle

function hasCycle(head) {
  let slow = head;
  let fast = head;

  while (fast !== null && fast.next !== null) {
    slow = slow.next;
    fast = fast.next.next;

    if (slow === fast) {
      return true; // slow กับ fast เจอกัน → มี cycle
    }
  }

  return false; // fast จบท้ายได้ → ไม่มี cycle
}

// Example
const a = { value: "A", next: null };
const b = { value: "B", next: null };
const c = { value: "C", next: null };
a.next = b; b.next = c; c.next = b; // cycle: A→B→C→B

console.log(hasCycle(a)); // true

• **Step 1:** ตั้ง slow = head, fast = head — ทั้งคู่เริ่มที่จุดเดียวกัน
• **Step 2:** ในแต่ละรอบ: slow = slow.next (1 ก้าว), fast = fast.next.next (2 ก้าว)
• **Step 3:** ถ้า slow === fast ณ จุดใด → มี cycle (เต่าและกระต่ายเจอกันในวงวน)
• **Step 4:** ถ้า fast === null หรือ fast.next === null → จบท้ายได้ ไม่มี cycle

ลองลงมือ — ฝึก Reverse & Find Middle

ลงมือ implement reverse linked list และหา middle node ด้วย slow/fast

Time Complexity สรุป — ทุก Operation บน Linked List

Use Cases — เมื่อไรควรใช้ Linked List

การเลือกโครงสร้างข้อมูลขึ้นอยู่กับ workload — ไม่มีโครงสร้างไหนดีที่สุดเสมอ ต่อไปนี้คือแนวทางเลือกใช้ linked list ในสถานการณ์จริง

ข้อผิดพลาดที่พบบ่อยและวิธีป้องกัน

• **ลืมอัปเดต pointer ทุกตัว** — หลัง insert/delete ต้องตรวจว่าทั้ง next, prev (doubly), head, และ tail ถูกอัปเดตครบ — ใช้เช็กลิสต์ทุกครั้งที่แก้ pointer
• **Lost reference** — เปลี่ยน next ของ current ก่อนเก็บ next เดิม → node ที่เหลือหายหมด — จำลำดับเสมอ: เก็บของเก่าก่อน แล้วค่อยเปลี่ยน pointer
• **Null pointer exception** — ก่อนใช้ .next หรือ .prev ต้องเช็กว่าไม่ใช่ null — โดยเฉพาะใน doubly list ที่ต้องเช็กทั้ง .next และ .prev
• **Infinite loop จาก cycle** — ตรวจว่า tail.next = null เสมอ — และตรวจว่าไม่มี next ชี้วกกลับไป node ก่อน
• **ลืมอัปเดต tail/size** — เมื่อใช้คลาสเก็บ tail หรือ size ไว้ ต้องอัปเดตทุกครั้งหลัง insert/delete — เขียน test case แยกเพื่อตรวจจับโดยเฉพาะ
• **เข้าใจผิดว่า insert/delete = O(1) เสมอ** — O(1) ที่ตัว node เองเท่านั้น — แต่ต้องหา node ก่อนทำ operation ซึ่งใช้ O(n) ถ้าไม่มี reference อยู่แล้ว
• **Singly vs Doubly เลือกผิด** — ใช้ doubly แม้ไม่ต้องเดินย้อนกลับ → เปลือง memory; ใช้ singly แล้วต้อง delete tail บ่อย → O(n) โดยไม่จำเป็น

ทบทวนความเข้าใจ — Patterns