Chương 7 - Linked List

Linked List (danh sách liên kết) là cấu trúc “đơn giản về lý thuyết, phức tạp về code”. Mỗi node trỏ tới node kế tiếp, vậy thôi - nhưng để code không bug, bạn cần thuộc lòng 5 trick nhỏ: dummy head, two pointers, đảo in-place, split-by-pivot, và phép gắn pointer chéo. Hết chương này, bạn sẽ thấy LL không còn đáng sợ.

Chương này có 12 bài - gấp đôi các chương cơ bản - vì pattern LL có nhiều biến thể quan trọng, từ Easy (Reverse, Merge, Cycle) đến Hard (Reverse k-Group, Sort, Reorder).

Mục tiêu chương

Sau chương này, bạn sẽ:

  • Thuộc 5 trick: dummy head, two pointers, reverse 3-pointer, split-process-merge, pointer relinking.
  • Phân biệt Floyd’s cycle detection vs hash-set detection.
  • Hiểu vì sao Doubly Linked List cần thiết cho LRU.
  • Tránh các bẫy: mất next, vòng lặp vô tình, quên cập nhật tail/head.

Khi nào dùng pattern này?

  • Đề bài cho input là head của linked list (đơn hoặc đôi).
  • Cần thao tác chèn / xoá node giữa danh sách (không như array, LL làm trong O(1) nếu có reference).
  • Yêu cầu O(1) extra space - không được copy ra mảng rồi xử lý.
  • Khi gặp bài “tìm node theo offset từ cuối”, “phát hiện chu trình”, “merge / split / đảo” → mặc định think linked list patterns.

5 trick phải thuộc lòng:

  1. Dummy head: tạo 1 node giả dummy.next = head, dùng prev = dummy. Tránh hàng tá if head is None.
  2. Two pointers (slow / fast): tìm giữa (1×, 2× tốc độ), phát hiện chu trình (Floyd), tìm offset từ cuối.
  3. Reverse in-place: 3 con trỏ prev / curr / nxt.
  4. Split → process → merge: pattern cho merge-sort, palindrome check, reorder.
  5. Pointer relinking: khi gắn a.next = b, luôn nhớ rời a khỏi vị trí cũ trước (cập nhật cả pointer “đi vào” và “đi ra” của a).

Định dạng input (áp dụng cho TẤT CẢ bài trong chương)

Mọi bài trong chương 7 (và 3.3, 15.5) đều dùng ListNode chuẩn của LeetCode:

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
  • Tham số head luôn là một node ListNode (hoặc None nếu list rỗng).
  • Trong sách dùng ký hiệu 1 → 2 → 3 → None để minh hoạ một linked list khởi tạo từ head = ListNode(1, ListNode(2, ListNode(3))).
  • Output trả về head mới (khi đảo / merge / split) hoặc mutate in-place khi đề bài yêu cầu rõ (“reorder”, “remove nth”, …).
  • Special variant: bài 7.8 Copy List with Random Pointer dùng Node mở rộng có thêm random pointer; bài 7.11 LRU dùng doubly linked list tự định nghĩa.

Template code 

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


def use_dummy(head: ListNode | None) -> ListNode | None:
    """Mẫu dummy head - bài hay có chèn/xoá node ở đầu."""
    dummy = ListNode(0, head)
    prev = dummy
    while prev.next:
        # ... thao tác trên prev.next ...
        prev = prev.next
    return dummy.next      # head có thể đã đổi


def find_middle(head: ListNode | None) -> ListNode | None:
    """Slow/fast pointers - tìm middle (LC 876)."""
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow


def reverse(head: ListNode | None) -> ListNode | None:
    """Reverse iterative - 3 con trỏ."""
    prev, curr = None, head
    while curr:
        curr.next, prev, curr = prev, curr, curr.next
    return prev

Bài tự luyện cuối chương

  • LC 86 - Partition List
  • LC 92 - Reverse Linked List II (đảo trong [left, right])
  • LC 109 - Convert Sorted List to BST
  • LC 142 - Linked List Cycle II (tìm node bắt đầu chu trình)
  • LC 160 - Intersection of Two Linked Lists
  • LC 328 - Odd Even Linked List
  • LC 445 - Add Two Numbers II (high digits first)

7.1 Reverse Linked List (LC 206) - bản iterative

Đề bài

Cho head của linked list đơn. Đảo ngược danh sách và trả về head mới. (Bài này đã có bản đệ quy ở Chương 3.3 - phần này tập trung vào bản iterative với O(1) space.)

Ví dụ 

Input:  head = 1 → 2 → 3 → 4 → 5 → None  (singly linked list)
Output: 5 → 4 → 3 → 2 → 1 → None

Ràng buộc

  • 0 <= số node <= 5000
  • -5000 <= node.val <= 5000

Clarifying questions

  • Có sửa node được không? → Có.
  • Linked list có vòng không? → Theo đề: không.

Hướng tiếp cận

3 con trỏ: - prev = node ngay trước curr trong danh sách kết quả. - curr = node đang xử lý. - nxt = sao lưu curr.next trước khi sửa.

Mỗi vòng: lật curr.next về prev, rồi dịch prev, curr về phía trước.

Hình minh hoạ với 1 → 2 → 3 → None:

Bắt đầu :   prev = None
            curr → 1 → 2 → 3 → None
                    
Vòng 1:     nxt = 2
            curr.next = prev   →   None ← 1   2 → 3 → None
            prev = curr = 1, curr = 2

Vòng 2:     nxt = 3
            curr.next = prev   →   None ← 1 ← 2   3 → None
            prev = 2, curr = 3

Vòng 3:     nxt = None
            curr.next = prev   →   None ← 1 ← 2 ← 3
            prev = 3, curr = None  → dừng

Trả prev = 3, danh sách: 3 → 2 → 1 → None

Code Python 3 

class Solution:
    def reverseList(self, head: ListNode | None) -> ListNode | None:
        prev, curr = None, head
        while curr:
            nxt = curr.next
            curr.next = prev
            prev = curr
            curr = nxt
        return prev

Pythonic 1 dòng inside loop: curr.next, prev, curr = prev, curr, curr.next. Tuple unpacking đánh giá RHS trước, không cần nxt tạm.

Phân tích độ phức tạp

  • Thời gian: O(n). Bộ nhớ: O(1).

Bình luận

  • Bản iterative vs đệ quy:
    • Iterative: O(1) space - best cho mọi case.
    • Đệ quy: O(n) stack - khi n lớn (5·10⁴+) sẽ RecursionError trong Python.
  • Bẫy: quên gán curr.next = prev trước khi dịch prev / curr → mất pointer.

Bài tự luyện liên quan

  • LC 92 - Reverse Linked List II.
  • LC 25 - Reverse Nodes in k-Group (bài 7.9).
  • LC 234 - Palindrome Linked List (bài 7.6).

7.2 Merge Two Sorted Lists (LC 21)

Đề bài

Cho 2 head của 2 linked list đã sort tăng dần. Trả về head của list gộp lại (cũng sort tăng).

Ví dụ 

Input:  l1 = 1 → 2 → 4,  l2 = 1 → 3 → 4
Output: 1 → 1 → 2 → 3 → 4 → 4

Ràng buộc

  • 0 <= len(list1), len(list2) <= 50
  • -100 <= node.val <= 100

Clarifying questions

  • Stable merge khi value bằng nhau? → Có (dùng <=).

Hướng tiếp cận

Iterative - dùng dummy head. Tạo dummy và tail = dummy. Mỗi vòng, gắn tail.next vào node nhỏ hơn của 2 list, dịch tail. Cuối cùng gắn phần đuôi còn dư.

Đệ quy (rất gọn nhưng O(n) stack):

if not l1: return l2
if not l2: return l1
if l1.val <= l2.val:
    l1.next = self.mergeTwoLists(l1.next, l2)
    return l1
else:
    l2.next = self.mergeTwoLists(l1, l2.next)
    return l2

Code Python 3 

class Solution:
    def mergeTwoLists(self, l1: ListNode | None, l2: ListNode | None) -> ListNode | None:
        dummy = ListNode()
        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     # gắn phần đuôi còn dư
        return dummy.next

Phân tích độ phức tạp

  • Thời gian: O(m + n). Bộ nhớ: O(1) iterative; O(m+n) stack đệ quy.

Bình luận

  • Dummy head ở đây tránh phải check if dummy is None mỗi vòng.
  • Follow-up: Merge k lists (LC 23) → dùng heap (Chương 15) hoặc divide-conquer.
  • Stable merge ↔︎ dùng <= (không phải <) → giữ thứ tự khi value bằng nhau.

Bài tự luyện liên quan

  • LC 23 - Merge k Sorted Lists.
  • LC 88 - Merge Sorted Array.
  • LC 148 - Sort List (bài 7.10).

7.3 Linked List Cycle (LC 141)

Đề bài

Cho head của linked list. Trả về True nếu có chu trình, ngược lại False. Yêu cầu: O(1) extra space.

Ví dụ 

Input:  head = [3, 2, 0, -4], cycle bắt đầu ở index 1
        3 → 2 → 0 → -4
            ↑________|
Output: True

Ràng buộc

  • 0 <= số node <= 10^4
  • -10^5 <= node.val <= 10^5

Clarifying questions

  • O(1) extra space? → Có (Floyd).
  • Có cần trả node bắt đầu cycle không? → Bài này không (xem LC 142).

Hướng tiếp cận

Brute force - Hash set, O(n) space. Lưu các node đã thấy.

Tối ưu - Floyd’s Tortoise and Hare, O(1) space.

Hai con trỏ slow (1×) và fast (2×). Nếu có chu trình, fast sẽ “đuổi kịp” slow trong vòng tròn (mỗi bước khoảng cách giữa 2 giảm 1). Nếu không, fast hết đường.

Hình minh hoạ - slow/fast trên chu trình:

Linked list:  3 → 2 → 0 → -4 → ⟲ (về 2)

Bước 0:  slow=3, fast=3
Bước 1:  slow=2, fast=0
Bước 2:  slow=0, fast=2     (fast đã quay vòng)
Bước 3:  slow=-4, fast=-4   ★ gặp nhau → return True

Trên chu trình dài L, slow đi 1 bước, fast đi 2 bước → khoảng cách
giảm 1 mỗi bước → tối đa L bước thì gặp.

Code Python 3 

class Solution:
    def hasCycle(self, head: ListNode | None) -> bool:
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow is fast:
                return True
        return False

Phân tích độ phức tạp

  • Thời gian: O(n). Bộ nhớ: O(1).

Bình luận

  • Tại sao gọi “tortoise & hare”? Slow (rùa) bước 1, fast (thỏ) bước 2.
  • Bẫy: dùng slow == fast (so sánh value) thay vì slow is fast (so sánh reference) → có thể sai khi 2 node khác nhưng val giống.
  • Follow-up: LC 142 - Linked List Cycle II - tìm node bắt đầu chu trình. Sau khi slow == fast, reset slow = head và đi cùng tốc độ 1 với fast, chúng sẽ gặp nhau tại node bắt đầu chu trình (chứng minh bằng đại số).

Bài tự luyện liên quan

  • LC 142 - Linked List Cycle II.
  • LC 160 - Intersection of Two Linked Lists.
  • LC 287 - Find the Duplicate Number (Floyd áp dụng trên số!).

7.4 Middle of the Linked List (LC 876)

Đề bài

Cho head. Trả về node giữa của linked list. Nếu có 2 node giữa (list chẵn), trả về cái thứ 2.

Ví dụ 

Input:  head = 1 → 2 → 3 → 4 → 5     (singly linked list)
Output: node có value 3 (giữa, thuộc về nửa sau khi length chẵn)
Input:  head = 1 → 2 → 3 → 4 → 5 → 6   (singly linked list, length chẵn)
Output: node có value 4 (giữa thứ 2)

Ràng buộc

  • 1 <= số node <= 100
  • 1 <= node.val <= 100

Clarifying questions

  • Có 2 middle node thì trả cái nào? → Cái thứ 2.

Hướng tiếp cận

Brute force - 2 lượt, O(n). Đếm độ dài, rồi đi đến giữa.

Tối ưu - Slow/fast 1 lượt, O(n). Khi fast chạm cuối, slow ở giữa.

Code Python 3 

class Solution:
    def middleNode(self, head: ListNode | None) -> ListNode | None:
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        return slow

Phân tích độ phức tạp

  • Thời gian: O(n). Bộ nhớ: O(1).

Bình luận

  • Kỹ thuật slow/fast sẽ tái xuất ở nhiều bài: Palindrome LL (7.6), Sort List (7.10), Reorder List (7.12) - tất cả đều cần tìm middle trước khi split.
  • Nếu yêu cầu là node thứ nhất trong 2 node giữa? → Đổi điều kiện loop: while fast.next and fast.next.next: (dừng 1 bước sớm hơn).

Bài tự luyện liên quan

  • LC 234 - Palindrome Linked List.
  • LC 143 - Reorder List.
  • LC 148 - Sort List.

7.5 Remove Nth Node From End of List (LC 19)

Đề bài

Cho head và số n. Xoá node thứ n tính từ cuối (1-indexed) và trả về head có thể đã đổi.

Ví dụ 

Input:  1 → 2 → 3 → 4 → 5, n = 2     → 1 → 2 → 3 → 5  (xoá node 4)
Input:  1, n = 1                     → None
Input:  1 → 2, n = 1                 → 1

Ràng buộc

  • 1 <= n <= 30
  • 1 <= n <= len(list)

Clarifying questions

  • n luôn ≤ độ dài list? → Có (theo đề).

Hướng tiếp cận

Brute force - 2 lượt. Đếm độ dài L, sau đó xoá node thứ L - n từ đầu.

Tối ưu - 1 lượt, two pointers cách nhau n. - Tạo dummy để xử lý case xoá head. - fast đi n bước trước. - Sau đó slow và fast cùng đi đến khi fast.next is None. Lúc đó slow.next chính là node cần xoá.

Hình minh hoạ với 1 → 2 → 3 → 4 → 5, n = 2:

Bắt đầu:  dummy → 1 → 2 → 3 → 4 → 5 → None
          slow                            
          fast                            

Sau khi fast đi n=2 bước:
          dummy → 1 → 2 → 3 → 4 → 5 → None
          slow        fast              

Cùng đi đến khi fast.next == None:
          dummy → 1 → 2 → 3 → 4 → 5 → None
                          slow      fast

slow.next = 4 → cần xoá. slow.next = slow.next.next.
          dummy → 1 → 2 → 3 → 5 → None  ✓

Code Python 3 

class Solution:
    def removeNthFromEnd(self, head: ListNode | None, n: int) -> ListNode | None:
        dummy = ListNode(0, head)
        slow = fast = dummy
        for _ in range(n):
            fast = fast.next
        while fast.next:
            slow = slow.next
            fast = fast.next
        slow.next = slow.next.next
        return dummy.next

Phân tích độ phức tạp

  • Thời gian: O(L). Bộ nhớ: O(1).

Bình luận

  • Vì sao dummy? Khi n == L, ta xoá head. Dummy giúp code thống nhất - slow sẽ là dummy, slow.next = slow.next.next đúng cho head mới.
  • Bẫy: quên dummy → phải special-case xoá head.

Bài tự luyện liên quan

  • LC 83 - Remove Duplicates from Sorted List.
  • LC 82 - Remove Duplicates from Sorted List II.
  • LC 1721 - Swapping Nodes in a Linked List.

7.6 Palindrome Linked List (LC 234)

Đề bài

Cho head của linked list đơn. Trả về True nếu giá trị các node tạo thành chuỗi palindrome. Yêu cầu: O(n) time, O(1) space.

Ví dụ 

Input:  head = 1 → 2 → 2 → 1     → Output: True   (palindrome)
Input:  head = 1 → 2             → Output: False  (1 ≠ 2)

Ràng buộc

  • 1 <= số node <= 10^5
  • 0 <= node.val <= 9

Clarifying questions

  • Có cho phép sửa list không? → Có (theo bài).
  • Có cần restore sau khi xong? → Theo phỏng vấn nên hỏi.

Hướng tiếp cận

Brute force - copy ra mảng + two pointers, O(n) space. Đơn giản, nhưng vi phạm O(1) space.

Tối ưu - Split + Reverse half + Compare, O(1) space. 1. Tìm middle (slow/fast). 2. Đảo nửa sau (in-place). 3. So sánh từng node giữa nửa đầu và nửa sau đã đảo. 4. (Optional) Khôi phục nửa sau (trong phỏng vấn thường khỏi cần).

Hình minh hoạ với 1 → 2 → 3 → 2 → 1:

Bước 1: tìm middle (slow ở node 3)
              1 → 2 → 3 → 2 → 1
                      ↑ slow

Bước 2: đảo nửa sau (từ slow.next = 2):
              1 → 2 → 3   1 → 2
              (nửa đầu)   (nửa sau đã đảo)

Bước 3: so sánh từng node:
              1 vs 1 ✓
              2 vs 2 ✓
        → True

Code Python 3 

class Solution:
    def isPalindrome(self, head: ListNode | None) -> bool:
        # 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, curr = None, slow
        while curr:
            curr.next, prev, curr = prev, curr, curr.next

        # 3. So sánh.
        left, right = head, prev
        while right:    # nửa sau đã đảo có thể ngắn hơn 1 node
            if left.val != right.val:
                return False
            left = left.next
            right = right.next
        return True

Phân tích độ phức tạp

  • Thời gian: O(n). Bộ nhớ: O(1).

Bình luận

  • Tại sao vòng while right: thay vì while left and right:? Vì sau khi split, nửa sau đã đảo luôn ngắn hơn hoặc bằng nửa đầu (do middle thuộc về nửa sau khi đảo). Nửa sau “chạm cuối trước” sẽ kết thúc loop.
  • Bẫy: quên xử lý list 1 node hoặc rỗng - code trên xử lý tự nhiên các trường hợp này.
  • Follow-up: nếu đề yêu cầu không được sửa linked list → phải dùng cách copy ra mảng O(n) space.

Bài tự luyện liên quan

  • LC 125 - Valid Palindrome (chuỗi, Chương 2).
  • LC 143 - Reorder List (cùng pattern split + reverse + merge).
  • LC 206 - Reverse Linked List.

7.7 Add Two Numbers (LC 2)

Đề bài

Cho 2 linked list đại diện 2 số nguyên không âm, digits lưu ngược (digit hàng đơn vị ở head). Trả về linked list = tổng 2 số (cũng theo dạng ngược).

Ví dụ 

Input:  l1 = 2 → 4 → 3   (đại diện 342)
        l2 = 5 → 6 → 4   (đại diện 465)
Output: 7 → 0 → 8         (đại diện 807 = 342 + 465)

Input:  l1 = 9 → 9 → 9 → 9 → 9 → 9 → 9
        l2 = 9 → 9 → 9 → 9
Output: 8 → 9 → 9 → 9 → 0 → 0 → 0 → 1

Ràng buộc

  • 1 <= len(l1), len(l2) <= 100
  • 0 <= node.val <= 9
  • Không leading zero (trừ số 0)

Clarifying questions

  • Mỗi số có leading zero không? → Không, trừ chính số 0.
  • Độ dài 2 list khác nhau? → Có thể.

Hướng tiếp cận

Mô phỏng cộng “tay”: đi đồng thời 2 list, giữ biến carry. Mỗi vòng: - total = (l1.val if l1 else 0) + (l2.val if l2 else 0) + carry

  • digit = total % 10, carry = total // 10. - Push digit vào kết quả; dịch l1, l2.

Vòng lặp dừng khi cả 2 cạn và carry == 0.

Code Python 3 

class Solution:
    def addTwoNumbers(self, l1: ListNode | None, l2: ListNode | None) -> ListNode | None:
        dummy = ListNode()
        tail = dummy
        carry = 0
        while l1 or l2 or carry:
            total = (l1.val if l1 else 0) + (l2.val if l2 else 0) + carry
            carry, digit = divmod(total, 10)
            tail.next = ListNode(digit)
            tail = tail.next
            if l1: l1 = l1.next
            if l2: l2 = l2.next
        return dummy.next

Phân tích độ phức tạp

  • Thời gian: O(max(m, n)). Bộ nhớ: O(max(m, n)) cho output.

Bình luận

  • Pattern “đi đồng thời + carry” xuất hiện nhiều trong các bài “add big numbers”: LC 415 (chuỗi), LC 67 (binary), LC 989 (mảng + int).
  • Bẫy: quên or carry ở vòng while → bỏ sót digit cuối khi 2 list cạn nhưng carry > 0 (ví dụ 5 + 5 = 10).
  • Follow-up - LC 445 (Add Two Numbers II): digits xếp xuôi (most-significant first). Cách: đảo cả 2 list trước, hoặc dùng 2 stack push các digit rồi pop ra.

Bài tự luyện liên quan

  • LC 445 - Add Two Numbers II.
  • LC 415 - Add Strings.
  • LC 989 - Add to Array-Form of Integer.

7.8 Copy List with Random Pointer (LC 138)

Đề bài

Cho linked list mà mỗi node ngoài next còn có random - trỏ tới node bất kỳ trong list (hoặc None). Hãy deep copy danh sách (mỗi node mới là 1 instance riêng, các random trỏ đúng vào node mới tương ứng).

Ví dụ 

Input (LC-style):
  head = [[7, null], [13, 0], [11, 4], [10, 2], [1, 0]]
  (mỗi phần tử [val, random_index]; random_index là chỉ số 0-based của node
   mà `random` trỏ tới, hoặc null nếu `random = None`)

  Tương ứng linked list:
        node 0      node 1      node 2      node 3      node 4
        val=7   →   val=13  →   val=11  →   val=10  →   val=1  →  None
        random:                                                    (next pointers)
          [0] → None
          [1] → node 0  (val 7)
          [2] → node 4  (val 1)
          [3] → node 2  (val 11)
          [4] → node 0  (val 7)

Output: deep copy của list trên - cùng val và cùng cấu trúc random,
        nhưng MỌI node là instance MỚI (không chia sẻ với input).

Output ở dạng LC array:
  [[7, null], [13, 0], [11, 4], [10, 2], [1, 0]]

Ràng buộc

  • 0 <= n <= 1000
  • -10^4 <= node.val <= 10^4

Clarifying questions

  • random pointer có thể trỏ về null không? → Có.
  • Sửa list gốc được không? → Tuỳ cách: hash map → không; interweave → có rồi restore.

Hướng tiếp cận

Cách 1 - Hash map “old → new”, O(n) time, O(n) space.

Lượt 1: tạo các node mới, lưu old_to_new[old] = new. Lượt 2: với mỗi old, gán new.next = old_to_new[old.next] và new.random = old_to_new[old.random].

Cách 2 - Interweave, O(n) time, O(1) extra space.

Trick rất nổi tiếng: 1. Lượt 1: chèn mỗi node copy ngay sau node gốc: A → A' → B → B' → C → C'. 2. Lượt 2: với mỗi node gốc A: gán A'.random = A.random.next (vì A.random.next chính là copy của A.random). 3. Lượt 3: tách 2 list ra.

Hình minh hoạ - Cách 2 với 3 node A, B, C:

Lượt 1 (chèn copy):
  A → A' → B → B' → C → C'

Lượt 2 (gán random):
  Giả sử A.random = C
  → A'.random = A.random.next = C.next = C'   (copy của C)  ✓

Lượt 3 (tách):
  Original:  A → B → C
  Copy:      A' → B' → C'

Code Python 3 

class Node:
    def __init__(self, val: int = 0, next=None, random=None):
        self.val = val
        self.next = next
        self.random = random


class Solution:
    """Cách 1 - Hash map. Code dễ debug nhất."""

    def copyRandomList(self, head: "Node | None") -> "Node | None":
        if not head:
            return None
        old_to_new: dict[Node, Node] = {}
        # Lượt 1: tạo node copy.
        cur = head
        while cur:
            old_to_new[cur] = Node(cur.val)
            cur = cur.next
        # Lượt 2: gán next/random.
        cur = head
        while cur:
            old_to_new[cur].next = old_to_new.get(cur.next)
            old_to_new[cur].random = old_to_new.get(cur.random)
            cur = cur.next
        return old_to_new[head]


class SolutionInterleave:
    """Cách 2 - Interweave, O(1) extra space."""

    def copyRandomList(self, head: "Node | None") -> "Node | None":
        if not head:
            return None
        # 1. Chèn copy ngay sau mỗi node gốc.
        cur = head
        while cur:
            cur.next = Node(cur.val, cur.next)
            cur = cur.next.next
        # 2. Gán random cho copy.
        cur = head
        while cur:
            if cur.random:
                cur.next.random = cur.random.next
            cur = cur.next.next
        # 3. Tách 2 list.
        new_head = head.next
        cur, copy = head, new_head
        while cur:
            cur.next = copy.next
            cur = cur.next
            copy.next = cur.next if cur else None
            copy = copy.next
        return new_head

Phân tích độ phức tạp

  • Cách 1: O(n) time, O(n) space.
  • Cách 2: O(n) time, O(1) extra space (không tính output).

Bình luận

  • Phỏng vấn nên trình bày Cách 1 trước (đơn giản, ai cũng hiểu), sau đó nhắc đến Cách 2 nếu interviewer hỏi tối ưu.
  • Bẫy Cách 2: quên tách list gốc → khi return, list gốc bị “biến dạng”.

Bài tự luyện liên quan

  • LC 133 - Clone Graph.
  • LC 1485 - Clone Binary Tree With Random Pointer.

7.9 Reverse Nodes in k-Group (LC 25)

Đề bài

Cho head và số k. Đảo ngược từng nhóm k node liên tiếp trong list. Nếu số node còn lại không đủ k thì giữ nguyên. Yêu cầu: O(1) extra space.

Ví dụ 

Input:  1 → 2 → 3 → 4 → 5, k = 2
Output: 2 → 1 → 4 → 3 → 5    (nhóm cuối chỉ có 1 node → giữ)

Input:  1 → 2 → 3 → 4 → 5, k = 3
Output: 3 → 2 → 1 → 4 → 5

Ràng buộc

  • 1 <= k <= n <= 5000
  • 0 <= node.val <= 1000

Clarifying questions

  • k > độ dài list? → Theo đề: 1 ≤ k ≤ length.

Hướng tiếp cận

Quy trình: 1. Đi k bước để xác định đuôi nhóm. Nếu không đủ k → break. 2. Đảo nhóm trong khoảng [head_nhóm, đuôi_nhóm]. 3. Khâu đầu nhóm đã đảo vào prev_group_tail, đuôi nhóm đã đảo trỏ tới next_group_head. 4. Cập nhật prev_group_tail để tiếp tục nhóm sau.

Hình minh hoạ với 1 → 2 → 3 → 4 → 5, k = 2:

Bắt đầu:    dummy → 1 → 2 → 3 → 4 → 5 → None
            prev

Nhóm 1: [1, 2]. Đảo → [2, 1].
            dummy → 2 → 1 → 3 → 4 → 5 → None
                        ↑
                       prev (= 1, tail của nhóm vừa đảo)

Nhóm 2: [3, 4]. Đảo → [4, 3].
            dummy → 2 → 1 → 4 → 3 → 5 → None
                                ↑
                               prev (= 3)

Nhóm 3: [5]. Chỉ 1 node → không đủ k=2 → giữ.
            dummy → 2 → 1 → 4 → 3 → 5 → None   ✓

Code Python 3 

class Solution:
    def reverseKGroup(self, head: ListNode | None, k: int) -> ListNode | None:
        dummy = ListNode(0, head)
        prev_group_tail = dummy

        while True:
            # 1. Tìm đuôi nhóm - đi k bước.
            kth = prev_group_tail
            for _ in range(k):
                kth = kth.next
                if not kth:
                    return dummy.next      # không đủ k → giữ nguyên

            group_next = kth.next
            # 2. Đảo từ prev_group_tail.next đến kth.
            prev, curr = group_next, prev_group_tail.next
            while curr is not group_next:
                curr.next, prev, curr = prev, curr, curr.next
            # 3. Khâu nhóm đã đảo vào.
            old_head = prev_group_tail.next
            prev_group_tail.next = kth
            prev_group_tail = old_head     # bây giờ là đuôi của nhóm đã đảo

Phân tích độ phức tạp

  • Thời gian: O(n) - mỗi node được đảo đúng 1 lần.
  • Bộ nhớ: O(1).

Bình luận

  • Đây là một trong những bài LL khó nhất vì pointer relinking nhiều bước.
  • Mẹo trên whiteboard: vẽ hình từng nhóm với prev_group_tail, kth, group_next rõ ràng trước khi viết code. Interviewer sẽ follow theo dễ.
  • Bẫy thường gặp: quên gán prev_group_tail = old_head cho vòng sau → đảo lại nhóm cũ.

Bài tự luyện liên quan

  • LC 24 - Swap Nodes in Pairs (chính là k = 2).
  • LC 92 - Reverse Linked List II.

7.10 Sort List (LC 148)

Đề bài

Sort linked list tăng dần với O(n log n) time và O(1) extra space (theo follow-up - chỉ tính call stack/aux, không tính node).

Ví dụ 

Input:  head = 4 → 2 → 1 → 3   (singly linked list)
Output: 1 → 2 → 3 → 4

Ràng buộc

  • 0 <= số node <= 5·10^4
  • -10^5 <= node.val <= 10^5

Clarifying questions

  • Stable sort? → Có với merge sort.
  • Bộ nhớ thực sự O(1)? → Top-down: O(log n) stack; bottom-up: O(1).

Hướng tiếp cận

O(n log n) ⇒ quicksort, mergesort, heapsort. Quicksort khó áp cho LL, heapsort cần O(n) extra. Mergesort là tự nhiên nhất:

  1. Split list thành 2 nửa (dùng slow/fast tìm middle, ngắt slow.next).
  2. Recurse trên cả 2 nửa.
  3. Merge 2 list đã sort (bài 7.2).

Top-down (đệ quy) đẹp về code nhưng tốn O(log n) stack. Bottom-up (iterative) đạt thật sự O(1) space - nhưng code phức tạp. Trong phỏng vấn, top-down là đủ tốt.

Hình minh hoạ với 4 → 2 → 1 → 3:

                   sort([4, 2, 1, 3])
                  /                  \
        sort([4, 2])             sort([1, 3])
         /        \                /        \
    [4]            [2]         [1]            [3]
       \          /                \          /
       merge → [2, 4]              merge → [1, 3]
                       \              /
                       merge → [1, 2, 3, 4]   ✓

Code Python 3 

class Solution:
    def sortList(self, head: ListNode | None) -> ListNode | None:
        if not head or not head.next:
            return head

        # 1. Split: tìm middle, ngắt đôi.
        slow, fast = head, head.next
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        mid = slow.next
        slow.next = None

        # 2. Recurse.
        left = self.sortList(head)
        right = self.sortList(mid)

        # 3. Merge.
        return self._merge(left, right)

    @staticmethod
    def _merge(l1: ListNode | None, l2: ListNode | None) -> ListNode | None:
        dummy = ListNode()
        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 or l2
        return dummy.next

Phân tích độ phức tạp

  • Thời gian: O(n log n).
  • Bộ nhớ: O(log n) cho stack (top-down). Bottom-up đạt O(1).

Bình luận

  • Tại sao fast = head.next (không phải head)? Vì với list 2 node a → b, ta muốn slow dừng ở a (nửa trái = [a], nửa phải = [b]). Nếu fast = head, slow dừng ở b → nửa phải rỗng → vòng lặp infinite.
  • Bẫy: quên slow.next = None → 2 nửa không tách ra → infinite recursion.

Bài tự luyện liên quan

  • LC 21 - Merge Two Sorted Lists.
  • LC 23 - Merge k Sorted Lists.
  • LC 147 - Insertion Sort List.

7.11 LRU Cache (LC 146) - recap

Bài này đã được giải đầy đủ ở Chương 6 - Hash Table (mục 6.6). Ở đây chúng ta chỉ tóm tắt nhanh pattern Doubly Linked List vốn là điểm nhấn của LL.

Đề bài

Thiết kế LRU Cache với get(key) và put(key, value) đều O(1). Khi vượt capacity → xoá key ít dùng gần nhất.

Ràng buộc

  • 1 <= capacity <= 3000
  • 0 <= key, value <= 10^4

Clarifying questions

  • Khi put key đã tồn tại? → Update value + đẩy thành MRU.
  • Thread-safe? → Không yêu cầu (theo LC).

Hướng tiếp cận: Doubly Linked List + Hash Map

LRU yêu cầu O(1) cho cả: - Lookup theo key → hash map. - Di chuyển 1 phần tử bất kỳ về đầu → doubly linked list (chỉ DLL mới cho phép unlink O(1) khi có reference).

Hình minh hoạ DLL state khi LRU eviction 

capacity = 2
Head sentinel - MRU end                LRU end - Tail sentinel
       │                                                  │
       ▼                                                  ▼
     ┌───┐    ┌──────┐    ┌──────┐    ┌──────┐    ┌───┐
     │ H │ ↔ │ K=4  │ ↔ │ K=3  │ ↔ │ K=1  │ ↔ │ T │
     └───┘    └──────┘    └──────┘    └──────┘    └───┘
                                          ▲
                          khi vượt capacity, xoá node này
                          (Tail.prev = LRU)

Hash map:  {1: node1, 3: node3, 4: node4}

Code Python 3 (pattern DLL) 

class Node:
    __slots__ = ("key", "val", "prev", "next")
    def __init__(self, key=0, val=0):
        self.key, self.val = key, val
        self.prev = self.next = None


# Hai sentinel head/tail giúp tránh hàng tá check None.
head, tail = Node(), Node()
head.next, tail.prev = tail, head

def _remove(node):              # O(1) - chỉ cần reference
    node.prev.next = node.next
    node.next.prev = node.prev

def _add_to_front(node):
    node.prev = head
    node.next = head.next
    head.next.prev = node
    head.next = node

Phân tích độ phức tạp

  • Thời gian: Get / Put: O(1) amortized.
  • Bộ nhớ: O(capacity).

Bình luận

  • Tại sao DLL chứ không Singly LL? Singly LL không cho O(1) xoá node bất kỳ - phải duyệt từ đầu để tìm prev.
  • Hai sentinel (head và tail giả) là idiomatic cho DLL. Không cần check node.prev is None hay node.next is None.
  • Xem giải đầy đủ tại 6.6 với cả phiên bản dùng OrderedDict (Python đã có sẵn DLL + hash trong nội bộ).

Bài tự luyện liên quan

  • LC 460 - LFU Cache.
  • LC 432 - All O(1) Data Structure.
  • LC 1670 - Design Front Middle Back Queue.

7.12 Reorder List (LC 143)

Đề bài

Cho linked list L: L0 → L1 → ... → Ln-1. Hãy sắp xếp lại thành:

L0 → Ln-1 → L1 → Ln-2 → L2 → Ln-3 → ...

In-place, không được tạo node mới.

Ví dụ 

Input:  head = 1 → 2 → 3 → 4
Output: 1 → 4 → 2 → 3 (mutate in-place)

Input:  head = 1 → 2 → 3 → 4 → 5
Output: 1 → 5 → 2 → 4 → 3   (mutate in-place)

Ràng buộc

  • 1 <= số node <= 5·10^4
  • 1 <= node.val <= 1000

Clarifying questions

  • Sửa list in-place? → Có (yêu cầu).
  • Có bảo toàn original node values? → Có, chỉ đổi pointer.

Hướng tiếp cận

3 bước chuẩn - vẫn là pattern “split → reverse → merge”:

  1. Tìm middle (slow/fast).
  2. Đảo nửa sau (in-place).
  3. Merge xen kẽ nửa đầu và nửa sau đã đảo.

Hình minh hoạ với 1 → 2 → 3 → 4 → 5:

Bước 1: tìm middle (slow ở 3)
            1 → 2 → 3 → 4 → 5

Bước 2: cắt đôi và đảo nửa sau:
            1 → 2 → 3      5 → 4
            (nửa đầu)      (nửa sau đã đảo)

Bước 3: merge xen kẽ:
            Lấy 1 từ trái → 1
            Lấy 5 từ phải → 1, 5
            Lấy 2 từ trái → 1, 5, 2
            Lấy 4 từ phải → 1, 5, 2, 4
            Lấy 3 từ trái → 1, 5, 2, 4, 3

Output: 1 → 5 → 2 → 4 → 3  ✓

Code Python 3 

class Solution:
    def reorderList(self, head: ListNode | None) -> None:
        if not head or not head.next:
            return

        # 1. Tìm middle.
        slow = fast = head
        while fast.next and fast.next.next:
            slow = slow.next
            fast = fast.next.next

        # 2. Đảo nửa sau (từ slow.next).
        second = slow.next
        slow.next = None      # cắt đôi
        prev, curr = None, second
        while curr:
            curr.next, prev, curr = prev, curr, curr.next
        second = prev          # head của nửa sau đã đảo

        # 3. Merge xen kẽ.
        first = head
        while second:
            tmp1, tmp2 = first.next, second.next
            first.next = second
            second.next = tmp1
            first, second = tmp1, tmp2

Phân tích độ phức tạp

  • Thời gian: O(n). Bộ nhớ: O(1).

Bình luận

  • Pattern “split + reverse + merge” xuất hiện trong rất nhiều bài LL hard. Một khi đã thuộc, bạn sẽ giải được Reorder, Palindrome, Rotate, Sort… gần như cùng template.
  • Bẫy: quên slow.next = None → khi merge sẽ tạo cycle.

Bài tự luyện liên quan

  • LC 234 - Palindrome Linked List.
  • LC 61 - Rotate List.
  • LC 148 - Sort List.

Tóm tắt chương & Quyết định

Pointer safety checklist

  1. Trước khi cắt a.next = b, đã lưu a.next cũ chưa?
  2. Có dummy/sentinel trỏ vào head chưa? (Cần khi head có thể đổi.)
  3. Vòng lặp while cur and cur.next: chú ý điều kiện kép cho 2 nút cuối.
  4. Sau khi reverse hoặc split, tail cũ đã .next = None chưa? (Tránh cycle.)
  5. Edge cases: list rỗng (head = None), 1 phần tử, k > len.

Dummy/sentinel pattern (cốt lõi) 

dummy = ListNode(0, head)
prev = dummy
# ... thao tác trên prev.next ...
return dummy.next

Dùng cho: Remove Nth From End, Merge Two Sorted, Partition, Odd Even, Reverse K-Group.

LRU (LC 146) bridge

  • Hash table trả lời “key này ở đâu?” → O(1) lookup.
  • Doubly linked list trả lời “nút nào ít dùng nhất?” → O(1) move/remove.
  • Hai cấu trúc bù trừ - ví dụ kinh điển kết hợp data structures.