02-Linked-List-Dummy-Node

Buổi 02 — Linked List & Dummy Node Pattern

Navigation

← 01-Complexity-and-Array | → 03-Stack-and-Queue Giai đoạn: Big Tech Foundation | Độ khó: ⭐⭐⭐

---

1. Analogy & Context

Mental Model

Hãy tưởng tượng một đoàn tàu. Mỗi toa tàu (node) chứa hàng hóa (val) và một móc nối (next) gắn với toa phía sau. Dummy head là một đầu máy rỗng đứng ở đầu tàu — nó không chở hành khách, nhưng giữ nguyên cấu trúc đoàn tàu khi ta thêm hay bỏ toa ở phía trước.

Vấn đề không có Dummy Node:

• Thêm node vào danh sách rỗng → phải kiểm tra head === null riêng.
• Xóa node đầu tiên → phải cập nhật head riêng.
• Mỗi thao tác đều có nhánh đặc biệt → code dài, dễ bug.

Giải pháp Dummy Node:

• Tạo một node “ảo” trước head thực sự.
• Mọi thao tác đều xử lý giống nhau — không còn case đặc biệt.
• Kết quả: return dummy.next để lấy head thực.

Khi nào dùng Dummy Node?

Bất cứ khi nào bạn cần thao tác tại đầu danh sách hoặc merge/build danh sách mới, dummy node là lựa chọn mặc định của FAANG engineers.

---

2. The FAANG Standard

Tại sao Linked List quan trọng ở FAANG?

• 30% số bài Medium trên LeetCode liên quan đến Linked List.
• Pointer manipulation dưới áp lực phỏng vấn là yếu tố phân biệt ứng viên.
• Code không dùng dummy node nhưng vẫn đúng → có thể chấp nhận được.
• Code dùng dummy node cleanly → signal của kỹ sư có kinh nghiệm.

Những gì interviewer đánh giá:

1. Correctness: Xử lý đúng empty list, single node, two nodes.
2. Clean pointer manipulation: Không mất reference, đúng thứ tự reassign.
3. No special cases: Dummy node pattern = ít nhánh if hơn.
4. Return value: Nhớ return dummy.next, không phải dummy.

Red Flags trong phỏng vấn

• Không test với empty list / single node → điểm trừ nặng.
• Dùng arr.indexOf() hoặc convert sang array → không hiểu bài.
• Viết code rồi mới vẽ diagram → nên làm ngược lại: diagram trước, code sau.

---

3. Visual Thinking

Cấu trúc Singly Linked List

graph LR
    A["val:1 | next:●"] -->|next| B["val:2 | next:●"]
    B -->|next| C["val:3 | next:●"]
    C -->|next| D["val:4 | next:null"]

    style A fill:#4A90D9,color:#fff
    style B fill:#4A90D9,color:#fff
    style C fill:#4A90D9,color:#fff
    style D fill:#4A90D9,color:#fff

WITHOUT vs WITH Dummy Node

graph TD
    subgraph WITHOUT["Without Dummy — 3 Cases"]
        W1["Case 1: Empty list → head = newNode"]
        W2["Case 2: Insert at head → newNode.next = head; head = newNode"]
        W3["Case 3: Insert middle → prev.next = newNode; newNode.next = curr"]
    end

    subgraph WITH["With Dummy — Always Same Operation"]
        Op["newNode.next = prev.next<br/>prev.next = newNode<br/>(prev always starts at dummy)"]
    end

    style WITHOUT fill:#FFE0E0
    style WITH fill:#E0FFE0

Dummy Node Pattern — Visual Flow

graph LR
    DH["dummy<br/>(sentinel)"] -->|next| N1["1"]
    N1 -->|next| N2["2"]
    N2 -->|next| N3["3"]
    N3 -->|next| NL["null"]

    CURR["curr = dummy"] -.->|traverses right| DH

    style DH fill:#FFD700,color:#000
    style CURR fill:#FF6B6B,color:#fff

---

4. TypeScript Template

4.1 — ListNode Class Definition

/**
 * Definition for singly-linked list node.
 * Đây là building block cơ bản — học thuộc cấu trúc này.
 */
class ListNode {
  val: number;
  next: ListNode | null;
 
  constructor(val: number = 0, next: ListNode | null = null) {
    this.val = val;
    this.next = next;
  }
}
 
/**
 * Helper: Tạo linked list từ array (dùng để test)
 * @example arrayToList([1,2,3]) → 1 → 2 → 3 → null
 */
function arrayToList(arr: number[]): ListNode | null {
  const dummy = new ListNode(0);
  let curr = dummy;
  for (const val of arr) {
    curr.next = new ListNode(val);
    curr = curr.next;
  }
  return dummy.next;
}
 
/**
 * Helper: Chuyển linked list thành array (dùng để debug)
 */
function listToArray(head: ListNode | null): number[] {
  const result: number[] = [];
  while (head !== null) {
    result.push(head.val);
    head = head.next;
  }
  return result;
}

4.2 — Reverse Linked List: Iterative & Recursive

/**
 * LeetCode #206 — Reverse Linked List
 *
 * ITERATIVE: 3-pointer technique
 * Tư duy: Tại mỗi bước, đảo chiều một mũi tên.
 * Cần 3 con trỏ vì khi đảo curr.next, ta mất đường đến node tiếp theo.
 *
 * Time: O(N) | Space: O(1)
 */
function reverseListIterative(head: ListNode | null): ListNode | null {
  let prev: ListNode | null = null;
  let curr: ListNode | null = head;
 
  while (curr !== null) {
    const nextTemp = curr.next; // 1. Lưu next trước khi mất
    curr.next = prev;           // 2. Đảo chiều mũi tên
    prev = curr;                // 3. Tiến prev lên
    curr = nextTemp;            // 4. Tiến curr lên
  }
 
  return prev; // prev là head mới khi curr = null
}
 
/**
 * RECURSIVE: Tin tưởng vào định nghĩa đệ quy.
 * "Giả sử tail đã được reverse đúng, tôi chỉ cần xử lý head."
 *
 * Time: O(N) | Space: O(N) — call stack
 *
 * Visualization cho [1 → 2 → 3 → 4 → 5]:
 *   reverseList(1) calls reverseList(2)
 *     reverseList(2) calls reverseList(3)
 *       ... calls reverseList(5) → returns 5
 *     5.next = 4, 4.next = null
 *   Returns: 5 → 4 → 3 → 2 → 1
 */
function reverseListRecursive(head: ListNode | null): ListNode | null {
  // Base case: empty list hoặc single node
  if (head === null || head.next === null) return head;
 
  // Đệ quy: reverse toàn bộ từ node thứ 2 trở đi
  const newHead = reverseListRecursive(head.next);
 
  // head.next vẫn trỏ đến tail của reversed list
  // Làm cho tail trỏ ngược lại head
  head.next.next = head;
  head.next = null; // Tránh cycle!
 
  return newHead;
}

4.3 — Merge Two Sorted Lists (Dummy Node Pattern)

/**
 * LeetCode #21 — Merge Two Sorted Lists
 *
 * PATTERN: Dummy node + pointer traversal
 * Dummy node loại bỏ việc xử lý "result list rỗng" riêng.
 *
 * Time: O(M + N) | Space: O(1)
 *
 * @param list1 - Danh sách đã được sort tăng dần
 * @param list2 - Danh sách đã được sort tăng dần
 * @returns Merged sorted list
 */
function mergeTwoLists(
  list1: ListNode | null,
  list2: ListNode | null
): ListNode | null {
  // Dummy node: curr bắt đầu từ đây, không cần check "result empty"
  const dummy = new ListNode(0);
  let curr = dummy;
 
  while (list1 !== null && list2 !== null) {
    if (list1.val <= list2.val) {
      curr.next = list1;
      list1 = list1.next;
    } else {
      curr.next = list2;
      list2 = list2.next;
    }
    curr = curr.next;
  }
 
  // Gắn phần còn lại (một trong hai đã hết)
  curr.next = list1 !== null ? list1 : list2;
 
  return dummy.next; // QUAN TRỌNG: return dummy.next, không phải dummy!
}

4.4 — Detect Cycle: Floyd’s Two-Pointer

/**
 * LeetCode #141 — Linked List Cycle
 *
 * ALGORITHM: Floyd's Tortoise and Hare
 * - slow đi 1 bước/lần, fast đi 2 bước/lần
 * - Nếu có cycle: fast sẽ "đuổi kịp" slow bên trong cycle
 * - Nếu không có cycle: fast sẽ reach null trước
 *
 * Tại sao chúng gặp nhau? Sau khi slow vào cycle, khoảng cách giữa
 * fast và slow giảm đi 1 mỗi bước → chắc chắn gặp nhau.
 *
 * Time: O(N) | Space: O(1)
 */
function hasCycle(head: ListNode | null): boolean {
  let slow: ListNode | null = head;
  let fast: ListNode | null = head;
 
  while (fast !== null && fast.next !== null) {
    slow = slow!.next;       // 1 bước
    fast = fast.next.next;   // 2 bước
 
    if (slow === fast) return true; // Gặp nhau → có cycle
  }
 
  return false; // fast reach null → không có cycle
}
 
/**
 * LeetCode #142 — Linked List Cycle II (Bonus: tìm node bắt đầu cycle)
 *
 * Sau khi slow và fast gặp nhau:
 * - Reset một pointer về head
 * - Di chuyển cả hai 1 bước/lần
 * - Nơi chúng gặp nhau = điểm bắt đầu cycle (math proof)
 */
function detectCycle(head: ListNode | null): ListNode | null {
  let slow: ListNode | null = head;
  let fast: ListNode | null = head;
 
  // Phase 1: Detect cycle
  while (fast !== null && fast.next !== null) {
    slow = slow!.next;
    fast = fast.next.next;
    if (slow === fast) break;
  }
 
  if (fast === null || fast.next === null) return null; // No cycle
 
  // Phase 2: Find entry point
  slow = head;
  while (slow !== fast) {
    slow = slow!.next;
    fast = fast!.next;
  }
 
  return slow; // Entry point of cycle
}

4.5 — Remove Nth From End: Two-Pointer Gap Trick

/**
 * LeetCode #19 — Remove Nth Node From End of List
 *
 * TRICK: Tạo khoảng cách N giữa fast và slow.
 * Khi fast đến cuối, slow đứng ngay TRƯỚC node cần xóa.
 *
 * Dummy node giúp xử lý case xóa node đầu tiên (khi n = length).
 *
 * Time: O(N) | Space: O(1) — One pass!
 *
 * @param head - Head of list
 * @param n - Xóa node thứ n từ cuối (1-indexed)
 */
function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
  const dummy = new ListNode(0);
  dummy.next = head;
 
  let fast: ListNode = dummy;
  let slow: ListNode = dummy;
 
  // Di chuyển fast đi n+1 bước để tạo khoảng cách n giữa fast và slow
  for (let i = 0; i <= n; i++) {
    fast = fast.next!;
  }
 
  // Di chuyển cả hai đến khi fast = null
  while (fast !== null) {
    fast = fast.next!;
    slow = slow.next!;
  }
 
  // slow đang ở node TRƯỚC node cần xóa
  slow.next = slow.next!.next;
 
  return dummy.next;
}

4.6 — Reverse Nodes in k-Group (Hard — LeetCode #25)

/**
 * LeetCode #25 — Reverse Nodes in k-Group
 *
 * YÊU CẦU: Reverse từng nhóm k nodes. Nếu nhóm cuối < k nodes, giữ nguyên.
 *
 * APPROACH:
 * 1. Dùng getKthNode để kiểm tra đủ k nodes không.
 * 2. Nếu đủ: reverse k nodes, nối với phần còn lại.
 * 3. Lặp lại cho nhóm tiếp theo.
 *
 * Time: O(N) | Space: O(1) — iterative approach
 *
 * Example: [1,2,3,4,5], k=2 → [2,1,4,3,5]
 * Example: [1,2,3,4,5], k=3 → [3,2,1,4,5]
 */
function reverseKGroup(head: ListNode | null, k: number): ListNode | null {
  /**
   * Trả về node thứ k tính từ node hiện tại.
   * Trả về null nếu không đủ k nodes.
   */
  const getKthNode = (node: ListNode | null, k: number): ListNode | null => {
    while (node !== null && k > 0) {
      node = node.next;
      k--;
    }
    return node;
  };
 
  const dummy = new ListNode(0);
  dummy.next = head;
  let groupPrev = dummy; // Node ngay trước nhóm hiện tại
 
  while (true) {
    // Lấy node thứ k trong nhóm (sẽ trở thành head mới)
    const kth = getKthNode(groupPrev, k);
    if (kth === null) break; // Không đủ k nodes → dừng
 
    const groupNext = kth.next; // Node đầu tiên của nhóm tiếp theo
 
    // Reverse k nodes trong nhóm [groupPrev.next ... kth]
    // prev kết thúc tại groupNext để nối liền danh sách
    let prev: ListNode | null = groupNext;
    let curr: ListNode | null = groupPrev.next;
 
    while (curr !== groupNext) {
      const nextTemp = curr!.next;
      curr!.next = prev;
      prev = curr;
      curr = nextTemp;
    }
 
    // Nối nhóm đã reverse vào danh sách
    const tmp = groupPrev.next!; // Head cũ = tail mới sau reverse
    groupPrev.next = kth;        // kth là head mới của nhóm đã reverse
    groupPrev = tmp;             // Tiến groupPrev đến tail vừa xử lý
  }
 
  return dummy.next;
}
 
/*
 * TRACE THROUGH với [1→2→3→4→5], k=2:
 *
 * Ban đầu: dummy → 1 → 2 → 3 → 4 → 5
 * groupPrev = dummy
 *
 * Vòng 1:
 *   kth = node(2), groupNext = node(3)
 *   Reverse [1→2] với prev bắt đầu = node(3):
 *     i=1: 1.next = 3, prev = node(1), curr = node(2)
 *     i=2: 2.next = 1, prev = node(2), curr = node(3) = groupNext → stop
 *   dummy.next = node(2), tmp = node(1) (head cũ, nay là tail)
 *   groupPrev = node(1)
 *   List: dummy → 2 → 1 → 3 → 4 → 5
 *
 * Vòng 2:
 *   kth = node(4), groupNext = node(5)
 *   Reverse [3→4]: tương tự
 *   List: dummy → 2 → 1 → 4 → 3 → 5
 *   groupPrev = node(3)
 *
 * Vòng 3:
 *   getKthNode(node(3), 2) → chỉ còn node(5), thiếu 1 → null → break
 *
 * Return: 2 → 1 → 4 → 3 → 5 ✓
 */

---

5. Complexity Deep-dive

So sánh Array vs Linked List

Thao tác	Array	Linked List	Ghi chú
Access by index	$O(1)$	$O(N)$	Array có random access, LL phải traverse
Search by value	$O(N)$	$O(N)$	Cả hai đều linear
Insert at head	$O(N)$	$O(1)$	Array phải shift toàn bộ
Insert at tail	$O(1)$*	$O(1)$**	*Amortized; **Cần giữ tail pointer
Insert at middle	$O(N)$	$O(N)$	LL cần traverse đến vị trí
Delete at head	$O(N)$	$O(1)$	Array phải shift toàn bộ
Delete at middle	$O(N)$	$O(N)$	Traverse + $O(1)$ xóa
Space overhead	$O(1)$ extra	$O(N)$ extra	Mỗi node LL cần lưu next pointer

Khi nào chọn Linked List over Array?

• Cần insert/delete thường xuyên tại đầu danh sách.
• Kích thước dữ liệu không biết trước (dynamic size).
• Implementing stack hay queue với guaranteed $O(1)$ mọi operation.

Space Complexity của các Algorithms

Algorithm	Time	Space	Ghi chú
Iterative reverse	$O(N)$	$O(1)$	Chỉ 3 pointers
Recursive reverse	$O(N)$	$O(N)$	N frames trên call stack
Floyd’s cycle detect	$O(N)$	$O(1)$	Chỉ 2 pointers
Remove Nth from end	$O(N)$	$O(1)$	One pass với gap trick
Reverse k-group	$O(N)$	$O(1)$	Iterative, không đệ quy

---

6. Edge Cases & Pitfalls

Lỗi 1: Mất Reference Trước Khi Reassign

// SAI — mất curr.next trước khi lưu lại
curr.next = prev;
prev = curr;
curr = curr.next; // curr.next đã bị thay đổi ở dòng đầu!
 
// ĐÚNG — lưu nextTemp trước khi thay đổi bất cứ thứ gì
const nextTemp = curr.next; // Lưu trước!
curr.next = prev;
prev = curr;
curr = nextTemp;

Lỗi 2: Null Pointer Exception trên .next.next

// SAI — fast.next có thể null, gây crash khi access .next trên null
fast = fast.next.next;
 
// ĐÚNG — guard cả fast và fast.next trước khi advance
while (fast !== null && fast.next !== null) {
  fast = fast.next.next;
}

Lỗi 3: Return dummy thay vì dummy.next

// SAI — trả về dummy node (node ảo, val = 0, không phải data thật)
return dummy;
 
// ĐÚNG — trả về head thực của danh sách
return dummy.next;

Pitfall: Off-by-one trong k-th from end

// Mục tiêu: slow dừng tại node TRƯỚC node cần xóa.
// Cần fast đi n+1 bước kể từ dummy (không phải n bước).
// Lý do: fast và slow cùng bắt đầu ở dummy,
//         sau n+1 bước fast hơn slow đúng n+1 vị trí.
//         Khi fast = null, slow đứng đúng trước node cần xóa.
for (let i = 0; i <= n; i++) { // <= n là đúng, không phải < n
  fast = fast.next!;
}

Pitfall: Tạo Cycle Khi Reverse Recursive

// Sau khi viết: head.next.next = head
// head.next vẫn trỏ đến chính head → tạo cycle vô hạn!
// BẮT BUỘC phải break cycle ngay sau đó:
head.next.next = head;
head.next = null; // Bẻ gãy cycle — KHÔNG được bỏ dòng này

---

7. Pattern Recognition

Nhận Diện Linked List Problems

Từ khóa	Pattern	Ví dụ
”reverse linked list”	3-pointer iterative	#206
”merge sorted lists”	Dummy node + two pointer	#21, #23
”detect cycle”	Floyd’s slow/fast	#141, #142
”k-th from end”	Two-pointer gap trick	#19
”palindrome linked list”	Find middle + reverse second half	#234
”intersection of two lists”	Length difference + two pointers	#160
”reverse in k-group”	Iterative group reversal	#25
”reorder list”	Find middle + reverse + merge	#143
”sort linked list”	Merge sort on LL	#148

Meta-Pattern

Hầu hết Linked List problems đều là biến thể của:

1. Traverse: slow/fast pointers — tìm middle, detect cycle, gap trick.
2. Modify: prev/curr/next pointers — reverse, remove, reorder.
3. Build: dummy node + curr pointer — merge, add numbers, partition.

---

8. Top LeetCode Problems

#	Tên	Độ khó	Pattern chính	Priority
206	Reverse Linked List	Easy	3-pointer	Must-do
21	Merge Two Sorted Lists	Easy	Dummy node	Must-do
141	Linked List Cycle	Easy	Floyd’s	Must-do
876	Middle of the Linked List	Easy	Slow/fast	Must-do
19	Remove Nth Node From End	Medium	Two-pointer gap	Must-do
143	Reorder List	Medium	Find middle + reverse + merge	High
142	Linked List Cycle II	Medium	Floyd’s phase 2	High
234	Palindrome Linked List	Medium	Find middle + reverse	High
2	Add Two Numbers	Medium	Dummy node + carry	Medium
25	Reverse Nodes in k-Group	Hard	Group reversal	Stretch

Lộ trình học tối ưu

1. Làm #206 (reverse) → hiểu 3-pointer.
2. Làm #21 (merge) → hiểu dummy node.
3. Làm #141 (cycle) → hiểu slow/fast.
4. Làm #19 (remove nth) → kết hợp dummy + gap trick.
5. Thử #25 (k-group) → tổng hợp tất cả kỹ năng.

---

9. Self-Assessment Checklist

Checklist trước khi chuyển sang buổi tiếp theo

Kiến thức nền:

• Giải thích được sự khác biệt Array vs Linked List (complexity + use case).
• Vẽ được diagram của dummy node pattern và giải thích tại sao nó hữu ích.
• Nắm được Floyd’s cycle detection — tại sao slow/fast chắc chắn gặp nhau?

Code từ memory (không nhìn):

• Viết được reverseList iterative với 3-pointer trong < 5 phút.
• Viết được mergeTwoLists với dummy node trong < 5 phút.
• Viết được hasCycle với Floyd’s trong < 3 phút.
• Viết được removeNthFromEnd với gap trick trong < 5 phút.

Hiểu sâu:

• Giải thích tại sao phải lưu nextTemp trước khi reassign.
• Giải thích off-by-one trong removeNthFromEnd — tại sao i <= n?
• Debug được: cho một linked list bị bug, tìm lỗi pointer manipulation.

Stretch goal:

• Solve được #25 Reverse Nodes in k-Group mà không cần nhìn solution.
• Implement được Merge Sort cho Linked List — $O(N\log N)$ time, $O(1)$ space.

---

Xem tiếp: 03-Stack-and-Queue — Stack là “call stack của đệ quy” được externalize