1.1 Linked List vs Array

Linked List có ưu thế khi cần thêm/xoá ở vị trí đã biết con trỏ; thua khi cần truy cập ngẫu nhiên. Trên LeetCode, đa số bài linked list là về thao tác con trỏ chứ không phải về performance.

1.2 ListNode trong Python

Định nghĩa chuẩn dùng ở mọi bài LeetCode:

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

Tạo và duyệt

# Tạo list 1 → 2 → 3
head = ListNode(1, ListNode(2, ListNode(3)))

# Duyệt
cur = head
while cur:
    print(cur.val)
    cur = cur.next

1.3 Dummy Node — Kỹ thuật vàng

Tạo một node "giả" đứng trước head để loại bỏ trường hợp đặc biệt khi xử lý đầu danh sách.

Vấn đề không có dummy

# Xoá mọi node có val == target
def removeElements(head, target):
    while head and head.val == target:    # case 1: xoá ở head
        head = head.next
    cur = head
    while cur and cur.next:               # case 2: xoá ở giữa
        if cur.next.val == target:
            cur.next = cur.next.next
        else:
            cur = cur.next
    return head

Dùng dummy — gộp 2 case thành 1

def removeElements(head, target):
    dummy = ListNode(0, head)
    cur = dummy
    while cur.next:
        if cur.next.val == target:
            cur.next = cur.next.next
        else:
            cur = cur.next
    return dummy.next

Code ngắn hơn, ít bug hơn. Quy tắc: bài nào có thể thay đổi head → dùng dummy.

1.4 Bốn bẫy con trỏ kinh điển

1. Mất reference (lost reference).

   cur.next = new_node    # nếu chưa lưu cur.next cũ trước, mất phần đuôi list!
   # Đúng:
   tmp = cur.next
   cur.next = new_node
   new_node.next = tmp

2. NullPointer / dereferencing None. Luôn check cur and cur.next trước khi truy cập cur.next.val.
3. Tạo chu kỳ vô tình. Khi nối node, đảm bảo cuối cùng có node chỉ về None. Một node.next = head là tạo chu kỳ.
4. Trả về sai head. Khi dùng dummy, trả dummy.next chứ không phải dummy hay head (head có thể đã bị xoá).

2.1 Pattern Fast & Slow Pointer

Ba ứng dụng kinh điển

1. Tìm middle của linked list trong 1 lần duyệt — không cần biết length.
2. Phát hiện chu kỳ — không cần Set (O(1) bộ nhớ).
3. Tìm node bắt đầu chu kỳ — Floyd's Tortoise and Hare đầy đủ.

Đây là phiên bản "trên linked list" của detect cycle đã giới thiệu ở Tuần 3 (Happy Number).

2.2 Worked Example 1 — Find Middle of Linked List

Đề (LeetCode #876): Cho head của linked list. Trả về node ở giữa. Nếu chẵn, trả node giữa thứ hai.

Cách ngây thơ

Pass 1: đếm n. Pass 2: đi n/2 bước. → 2 lần duyệt.

Fast & Slow — 1 lần duyệt

def middleNode(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow

Trace với 1 → 2 → 3 → 4 → 5

Trả về node 3. Time O(n), Space O(1).

2.3 Worked Example 2 — Linked List Cycle

Đề (LeetCode #141): Cho head. Trả True nếu danh sách có chu kỳ.

Approach 1 — HashSet

def hasCycle(head):
    seen = set()
    cur = head
    while cur:
        if cur in seen: return True
        seen.add(cur)
        cur = cur.next
    return False
# Time O(n), Space O(n)

Approach 2 — Fast & Slow (tốt hơn về space)

def hasCycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True
    return False
# Time O(n), Space O(1)

2.4 Vì sao Fast & Slow phát hiện được chu kỳ?

Trực giác — Đường đua tròn

Tưởng tượng hai vận động viên chạy trên đường đua tròn. Một người chạy 1 ô/giây, một người 2 ô/giây. Người chạy nhanh sẽ vượt người chạy chậm tròn vòng. Khi vượt, hai người gặp nhau.

Lý do toán học

Trong chu kỳ, khoảng cách fast − slow tăng đúng 1 mỗi bước (mod cycle length). Sau hữu hạn bước, khoảng cách = cycle length ≡ 0 → fast bắt kịp slow.

2.5 Worked Example 3 — Linked List Cycle II

Đề (LeetCode #142): Trả về node bắt đầu chu kỳ. None nếu không có.

Floyd's Tortoise and Hare — đầy đủ

def detectCycle(head):
    slow = fast = head
    # Pha 1: phát hiện chu kỳ
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            break
    else:
        return None                # không gặp nhau → không có chu kỳ
    if not (fast and fast.next):
        return None

    # Pha 2: tìm node bắt đầu
    slow = head
    while slow != fast:
        slow = slow.next
        fast = fast.next
    return slow

Time O(n), Space O(1).

2.6 Floyd's Algorithm — Chứng minh bằng toán

Đây là chứng minh kinh điển — sinh viên cần hiểu để không phải học vẹt.

Đặt tên các đoạn

• L1 = quãng đường từ head đến node bắt đầu chu kỳ.
• L2 = quãng đường từ node bắt đầu đến nơi slow gặp fast.
• C = chiều dài chu kỳ.

Lập luận

Khi gặp nhau, slow đã đi L1 + L2 bước. fast đã đi gấp đôi: 2(L1 + L2). Đồng thời fast đi nhiều hơn slow đúng k vòng chu kỳ:

Tức: từ điểm gặp nhau, đi thêm L1 bước (= kC − L2 bước) sẽ tới node bắt đầu chu kỳ.

Đó là lý do: sau pha 1, đặt slow về head, cả hai đi cùng tốc độ 1 bước/lần — sẽ gặp ở node bắt đầu.

2.7 Worked Example 4 — Happy Number Revisit (O(1) space)

Tuần 3 đã làm bằng set với O(log n) space. Giờ áp dụng Fast & Slow để giảm xuống O(1) space.

Quan sát: hàm "tổng bình phương chữ số" tạo ra một chuỗi giá trị như linked list ảo. Phát hiện chu kỳ trên chuỗi này tương đương với phát hiện chu kỳ trên linked list.

def isHappy(n):
    def step(x):
        s = 0
        while x:
            x, d = divmod(x, 10)
            s += d * d
        return s

    slow = n
    fast = step(n)
    while fast != 1 and slow != fast:
        slow = step(slow)
        fast = step(step(fast))
    return fast == 1

Time O(log n), Space O(1).

Knowledge Check — Fast & Slow

3.1 Pattern 3-pointer Reverse

Đảo linked list = lật ngược hướng của mọi next pointer. Cần 3 con trỏ cùng lúc:

• prev — node phía sau (theo hướng đảo).
• cur — node đang xử lý.
• next_node — lưu node kế trước khi cắt.

Bốn dòng kinh điển

next_node = cur.next     # lưu kẻo mất
cur.next = prev          # lật ngược
prev = cur               # tiến prev
cur = next_node          # tiến cur

3.2 Worked Example 5 — Reverse Linked List (Iterative)

Đề (LeetCode #206): Đảo ngược linked list, trả về head mới.

def reverseList(head):
    prev = None
    cur = head
    while cur:
        next_node = cur.next
        cur.next = prev
        prev = cur
        cur = next_node
    return prev

Trace với 1 → 2 → 3 → None

Trả về prev = 3. Time O(n), Space O(1).

3.3 Reverse Linked List — Recursive Version

def reverseList(head):
    if not head or not head.next:
        return head
    new_head = reverseList(head.next)
    head.next.next = head        # lật pointer
    head.next = None             # cắt nối cũ
    return new_head

Hình dung

Ý tưởng: giả sử đã đảo được phần đuôi head.next → ... → None thành ... → head.next. Bây giờ chỉ cần nối head.next.next = head và cắt head.next = None.

So sánh

3.4 Worked Example 6 — Reverse Linked List II

Đề (LeetCode #92): Đảo ngược các node từ vị trí left đến right (1-indexed). Một lần duyệt.

Kết hợp dummy node + 3-pointer reverse

def reverseBetween(head, left, right):
    dummy = ListNode(0, head)
    prev = dummy
    # Bước 1: di chuyển prev tới node đứng trước vị trí left
    for _ in range(left - 1):
        prev = prev.next
    # Bước 2: đảo (right - left) liên kết bằng "head insertion"
    cur = prev.next
    for _ in range(right - left):
        next_node = cur.next
        cur.next = next_node.next
        next_node.next = prev.next
        prev.next = next_node
    return dummy.next

Time O(n), Space O(1).

3.5 Worked Example 7 — Palindrome Linked List

Đề (LeetCode #234): Trả True nếu linked list là palindrome. Yêu cầu O(1) bộ nhớ phụ.

Combo của 3 kỹ thuật

1. Fast & Slow để tìm middle.
2. Reverse nửa sau.
3. So sánh nửa đầu với nửa sau đã đảo.

def isPalindrome(head):
    # 1. Tìm middle
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    # 2. Đảo nửa sau (bắt đầu từ slow)
    prev = None
    cur = slow
    while cur:
        nxt = cur.next
        cur.next = prev
        prev = cur
        cur = nxt
    # 3. So sánh
    left, right = head, prev
    while right:
        if left.val != right.val: return False
        left = left.next
        right = right.next
    return True

Time O(n), Space O(1).

Knowledge Check — Reverse

4.1 Pattern Merge với Dummy Node

dummy = ListNode(0)
tail = dummy
while <còn nguồn>:
    chosen = pick_smallest(...)
    tail.next = chosen
    tail = tail.next
    advance source pointer
tail.next = remaining        # nối phần dư
return dummy.next

Ý tưởng: dummy là điểm tựa, tail luôn trỏ đến node cuối của output. Chỉ cần "móc" node mới vào tail.next rồi tiến tail.

Ưu điểm của dummy

• Không có case đặc biệt cho head — code thống nhất.
• Output head được lấy bằng dummy.next.
• Áp dụng được cho merge, partition, concat.

4.2 Worked Example 8 — Merge Two Sorted Lists

Đề (LeetCode #21): Cho hai linked list đã sort. Merge thành một list sort, dùng các node có sẵn (không tạo node mới).

def mergeTwoLists(l1, l2):
    dummy = ListNode(0)
    tail = dummy
    while l1 and l2:
        if l1.val <= l2.val:
            tail.next = l1
            l1 = l1.next
        else:
            tail.next = l2
            l2 = l2.next
        tail = tail.next
    tail.next = l1 if l1 else l2     # nối phần dư
    return dummy.next

Trace với l1: 1→3→5, l2: 2→4

Time O(n+m), Space O(1).

4.3 Worked Example 9 — Remove Nth Node From End

Đề (LeetCode #19): Xoá node thứ n tính từ cuối. Một lần duyệt.

Kỹ thuật "Two pointer with gap"

Đây là biến thể của Fast & Slow — nhưng cùng tốc độ với khoảng cách cố định n. Khi fast tới cuối, slow đang ở vị trí cần xoá.

def removeNthFromEnd(head, n):
    dummy = ListNode(0, head)
    fast = slow = dummy
    # Đẩy fast đi n+1 bước
    for _ in range(n + 1):
        fast = fast.next
    # Cùng đi đến khi fast = None
    while fast:
        fast = fast.next
        slow = slow.next
    # slow.next là node cần xoá
    slow.next = slow.next.next
    return dummy.next

Vì sao n+1 bước, không phải n?

Để slow dừng ở node trước node cần xoá (cần ref để cắt). Khoảng cách fast − slow = n+1 → khi fast = None, slow ở vị trí n+1 từ cuối → tức trước node thứ n.

Time O(n) một lần duyệt, Space O(1).

4.4 Worked Example 10 — Reorder List (bài "boss" của tuần)

Đề (LeetCode #143): Cho L: L₀ → L₁ → ... → Lₙ₋₁ → Lₙ. Đổi thành L₀ → Lₙ → L₁ → Lₙ₋₁ → L₂ → ... Tại chỗ.

Ví dụ: 1→2→3→4→5 → 1→5→2→4→3.

3 pha — kết hợp toàn bộ kỹ thuật của tuần

def reorderList(head):
    if not head or not head.next: return
    # PHA 1: tìm middle
    slow = fast = head
    while fast.next and fast.next.next:
        slow = slow.next
        fast = fast.next.next
    # PHA 2: đảo nửa sau
    prev, cur = None, slow.next
    slow.next = None                          # cắt list thành 2 nửa
    while cur:
        nxt = cur.next; cur.next = prev
        prev = cur; cur = nxt
    # PHA 3: đan xen 2 list
    first, second = head, prev
    while second:
        tmp1, tmp2 = first.next, second.next
        first.next = second
        second.next = tmp1
        first, second = tmp1, tmp2

Time O(n), Space O(1).

5.1 Decision Tree — Linked List

Ba câu hỏi trước khi code

1. Bài có thể thay đổi head không? → Cần dummy.
2. Bài có truy cập cur.next.next không? → Cần check cur.next.
3. Bài có cần đảo ngược một phần không? → 3-pointer hoặc head insertion.

Tổng kết Tuần 5

Đã học

• Linked List basics: ListNode, dummy node, bốn bẫy con trỏ.
• Fast & Slow: middle, cycle detection, Floyd's full algorithm với chứng minh toán học.
• Reverse: 3-pointer iterative + recursive; reverse một đoạn với head insertion.
• Merge: dummy node làm điểm tựa; áp dụng cho remove, partition, đan xen.
• Two pointer with gap: variant của fast/slow để xoá node thứ n từ cuối trong 1 lần duyệt.
• Combo bài "boss": Palindrome LL, Reorder List = phân rã thành 3 pattern cơ bản.

Bài về nhà (12 bài)

1. LeetCode #876 — Middle of the Linked List
2. LeetCode #141 — Linked List Cycle
3. LeetCode #142 — Linked List Cycle II (Floyd's full)
4. LeetCode #202 — Happy Number (code lại với O(1) space)
5. LeetCode #206 — Reverse Linked List (cả iterative + recursive)
6. LeetCode #92 — Reverse Linked List II
7. LeetCode #234 — Palindrome Linked List
8. LeetCode #21 — Merge Two Sorted Lists
9. LeetCode #19 — Remove Nth Node From End of List
10. LeetCode #143 — Reorder List (boss)
11. LeetCode #2 — Add Two Numbers
12. LeetCode #160 — Intersection of Two Linked Lists