Bỏ qua

Danh sách liên kết, Ngăn xếp, và Hàng đợi

Danh sách liên kết, ngăn xếp và hàng đợi là những khối xây dựng cho các cấu trúc dữ liệu phức tạp hơn. Tệp này trình bày cơ chế hoạt động của chúng, sau đó xây dựng các mẫu chủ chốt: con trỏ nhanh/chậm, ngăn xếp đơn điệu, và hàng đợi ưu tiên dựa trên heap, thông qua các bài toán tăng dần độ khó kèm các cạm bẫy thường gặp ở mỗi bước.

  • Mảng cung cấp truy cập ngẫu nhiên nhanh nhưng chèn đắt đỏ. Danh sách liên kết cung cấp chèn nhanh nhưng không có truy cập ngẫu nhiên. Ngăn xếp và hàng đợi giới hạn truy cập ở một hoặc hai đầu, và chính sự giới hạn này làm chúng mạnh mẽ: bằng cách hạn chế những gì bạn có thể làm, chúng đơn giản hóa những gì bạn cần suy nghĩ.

Danh sách liên kết (Linked Lists)

  • Một danh sách liên kết đơn (singly linked list) là một chuỗi các node. Mỗi node lưu một giá trị và một con trỏ đến node tiếp theo. Node cuối cùng trỏ tới null.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

  • Lợi thế so với mảng: chèn hoặc xóa tại một vị trí đã biết là \(O(1)\) (chỉ cần trỏ lại các con trỏ). Không cần dịch chuyển phần tử.

  • Bất lợi: truy cập phần tử \(i\) cần duyệt \(O(i)\) (không có truy cập ngẫu nhiên). Tính định xứ bộ nhớ đệm kém (các node nằm rải rác trong bộ nhớ).

  • Danh sách liên kết đôi (doubly linked lists) thêm một con trỏ prev, cho phép duyệt ngược. Được dùng trong bộ nhớ đệm LRU (xóa bất kỳ node nào trong thời gian hằng số) và lịch sử trình duyệt (quay lại/tiến tới).

Thao tác Đơn Đôi
Truy cập theo chỉ số \(O(n)\) \(O(n)\)
Chèn tại đầu \(O(1)\) \(O(1)\)
Chèn tại đuôi \(O(n)\) hoặc \(O(1)\)* \(O(1)\)
Xóa node cho trước \(O(n)\)** \(O(1)\)
Tìm kiếm \(O(n)\) \(O(n)\)

*với con trỏ đuôi. **cần node trước, đòi hỏi duyệt.

  • Node giả (sentinel nodes) (đầu/đuôi giả) đơn giản hóa các trường hợp đặc biệt. Không có đầu giả, việc chèn tại đầu hoặc xóa đầu yêu cầu code trường hợp đặc biệt. Với đầu giả, mọi node thực đều có một node trước.
# Không có đầu giả: trường hợp đặc biệt cho xóa đầu
def delete_head(head):
    if not head:
        return None
    return head.next

# Có đầu giả: logic đồng nhất
dummy = ListNode(0)
dummy.next = head
# giờ mọi xóa đều là: prev.next = prev.next.next
  • Cạm bẫy: quên xử lý danh sách rỗng (head is None) hoặc danh sách một phần tử. Luôn kiểm tra các trường hợp biên này.

Mẫu: Con trỏ Nhanh và Chậm (Floyd)

  • Dùng hai con trỏ di chuyển với tốc độ khác nhau để phát hiện các tính chất của danh sách liên kết. Con trỏ chậm di chuyển một bước một lần; con trỏ nhanh di chuyển hai bước.

Dễ: Phát hiện Vòng trong Danh sách liên kết

  • Bài toán: xác định một danh sách liên kết có vòng (cycle) hay không.

  • Mẫu: nếu có vòng, con trỏ nhanh cuối cùng sẽ vượt con trỏ chậm (chúng sẽ gặp nhau). Nếu không có vòng, con trỏ nhanh đến null.

def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True
    return False

  • Tại sao nó hoạt động: nếu vòng có độ dài \(c\), con trỏ nhanh thu hẹp khoảng cách 1 node mỗi bước. Chúng phải gặp nhau trong vòng \(c\) bước kể từ khi con trỏ chậm vào vòng.

  • Cạm bẫy: kiểm tra fast and fast.next (không chỉ fast.next). Nếu fast là None, gọi fast.next sẽ crash.

Trung bình: Tìm Node Ở giữa Danh sách liên kết

  • Bài toán: trả về node ở giữa.

  • Mẫu: khi con trỏ nhanh đến cuối, con trỏ chậm đang ở giữa.

def find_middle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow  # slow ở giữa (hoặc giữa thứ hai nếu độ dài chẵn)

Trung bình: Tìm Điểm Bắt đầu Vòng

  • Bài toán: trả về node nơi vòng bắt đầu.

  • Mẫu: sau khi con trỏ nhanh và chậm gặp nhau, đặt lại một con trỏ về đầu. Di chuyển cả hai với tốc độ 1. Chúng gặp nhau tại điểm bắt đầu vòng.

def detect_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            # đưa một con trỏ về đầu
            slow = head
            while slow != fast:
                slow = slow.next
                fast = fast.next
            return slow
    return None
  • Tại sao nó hoạt động: gọi khoảng cách từ đầu đến điểm bắt đầu vòng là \(a\), và khoảng cách từ điểm bắt đầu vòng đến điểm gặp nhau là \(b\). Con trỏ chậm đi được \(a + b\). Con trỏ nhanh đi được \(2(a + b)\). Hiệu số là một vòng đầy đủ: \(a + b = c\) (độ dài vòng). Vậy \(a = c - b\): khoảng cách từ đầu đến điểm bắt đầu vòng bằng khoảng cách từ điểm gặp nhau đến điểm bắt đầu vòng (đi về phía trước vòng quanh vòng).

Khó: Đảo ngược Danh sách liên kết theo từng Nhóm K

  • Bài toán: đảo ngược mỗi \(k\) node liên tiếp trong một danh sách liên kết.
def reverse_k_group(head, k):
    # kiểm tra xem có đủ k node không
    node = head
    for _ in range(k):
        if not node:
            return head
        node = node.next

    # đảo ngược k node
    prev, curr = None, head
    for _ in range(k):
        nxt = curr.next
        curr.next = prev
        prev = curr
        curr = nxt

    # head giờ là đuôi của nhóm đã đảo ngược
    # xử lý đệ quy phần còn lại
    head.next = reverse_k_group(curr, k)
    return prev  # prev là đầu mới của nhóm này
  • Cạm bẫy: khuôn mẫu đảo ngược tại chỗ (prev, curr, nxt) đáng để ghi nhớ. Hãy vẽ nó ra: ở mỗi bước, bạn trỏ curr.next ngược về prev, rồi tiến cả ba con trỏ. Sai thứ tự sẽ làm hỏng danh sách.

Ngăn xếp (Stacks)

  • Một ngăn xếp (stack) là LIFO (Last In, First Out): phần tử được thêm vào gần nhất sẽ bị loại bỏ đầu tiên. Hãy nghĩ như một chồng đĩa.

  • Các thao tác: push(x) thêm vào đỉnh, pop() lấy ra từ đỉnh, peek() nhìn vào đỉnh mà không lấy ra. Tất cả đều \(O(1)\).

  • Ngăn xếp là cấu trúc ngầm đằng sau đệ quy (ngăn xếp lời gọi), đánh giá biểu thức (chuyển đổi trung tố sang hậu tố), và các thao tác hoàn tác (undo) (mỗi hành động được đẩy lên, undo bốc cái cuối cùng ra).

Dễ: Dấu ngoặc hợp lệ

  • Bài toán: cho một chuỗi các dấu ngoặc ()[]{}, xác định xem chúng có cân bằng hay không.

  • Mẫu: đẩy các dấu ngoặc mở vào ngăn xếp. Khi thấy một dấu ngoặc đóng, kiểm tra xem đỉnh ngăn xếp có phải là dấu ngoặc mở tương ứng không.

def is_valid(s):
    stack = []
    matching = {')': '(', ']': '[', '}': '{'}

    for char in s:
        if char in matching:
            if not stack or stack[-1] != matching[char]:
                return False
            stack.pop()
        else:
            stack.append(char)

    return len(stack) == 0
  • Cạm bẫy: quên len(stack) == 0 ở cuối. Chuỗi "(((" không có dấu hiệu sai nhưng không hợp lệ vì còn dấu ngoặc chưa đóng.

Mẫu: Ngăn xếp Đơn điệu (Monotonic Stack)

  • Một ngăn xếp đơn điệu duy trì các phần tử theo thứ tự sắp xếp (tăng dần hoặc giảm dần). Khi một phần tử mới vi phạm thứ tự, bạn bốc các phần tử cho đến khi thứ tự được phục hồi.

  • Khi nào dùng: các bài toán hỏi "với mỗi phần tử, tìm phần tử lớn hơn/nhỏ hơn tiếp theo/trước đó." Ngăn xếp cho \(O(n)\) tổng cộng vì mỗi phần tử được đẩy và bốc nhiều nhất một lần.

Trung bình: Daily Temperatures

  • Bài toán: cho nhiệt độ hàng ngày, với mỗi ngày tìm xem có bao nhiêu ngày cho đến khi nhiệt độ ấm hơn.

  • Mẫu: dùng một ngăn xếp các chỉ số. Khi nhiệt độ hiện tại cao hơn đỉnh ngăn xếp, bốc và ghi lại khoảng cách.

def daily_temperatures(temperatures):
    n = len(temperatures)
    result = [0] * n
    stack = []  # ngăn xếp các chỉ số, nhiệt độ theo thứ tự giảm dần

    for i in range(n):
        while stack and temperatures[i] > temperatures[stack[-1]]:
            prev = stack.pop()
            result[prev] = i - prev
        stack.append(i)

    return result

  • Mỗi phần tử được đẩy một lần và bốc nhiều nhất một lần: \(O(n)\) tổng cộng.

  • Cạm bẫy: lưu chỉ số trên ngăn xếp (không phải giá trị). Bạn cần chỉ số để tính khoảng cách.

Khó: Hình chữ nhật Lớn nhất trong Biểu đồ

  • Bài toán: cho một mảng chiều cao các cột, tìm diện tích hình chữ nhật lớn nhất.

  • Mẫu: với mỗi cột, tìm xem nó có thể mở rộng bao xa về trái và phải (nghĩa là cột ngắn hơn gần nhất ở mỗi bên). Một ngăn xếp đơn điệu tăng dần theo dõi điều này một cách hiệu quả.

def largest_rectangle(heights):
    stack = []  # ngăn xếp các chỉ số, chiều cao theo thứ tự tăng dần
    max_area = 0
    heights.append(0)  # sentinel để xả ngăn xếp ở cuối

    for i, h in enumerate(heights):
        start = i
        while stack and stack[-1][1] > h:
            idx, height = stack.pop()
            max_area = max(max_area, height * (i - idx))
            start = idx  # cột này có thể mở rộng về đến nơi cột bị bốc bắt đầu
        stack.append((start, h))

    heights.pop()  # xóa sentinel
    return max_area

  • Cạm bẫy: dòng start = idx rất tinh tế. Khi ta bốc một cột cao hơn cột hiện tại, cột hiện tại có thể mở rộng ngược về nơi cột bị bốc bắt đầu (vì mọi cột ở giữa đều cao ít nhất bằng cột đã bốc). Thiếu dòng này sẽ cho diện tích sai.

  • Cạm bẫy: sentinel heights.append(0) đảm bảo mọi cột còn lại trong ngăn xếp được xử lý. Thiếu nó, các cột không bao giờ gặp một cột ngắn hơn bên phải sẽ bị bỏ sót.

Hàng đợi (Queues)

  • Một hàng đợi (queue) là FIFO (First In, First Out): các phần tử được thêm vào sau và lấy ra từ trước. Hãy nghĩ như một hàng xếp tại cửa hàng.

  • Một deque (hàng đợi hai đầu) hỗ trợ chèn và xóa \(O(1)\) ở cả hai đầu. collections.deque của Python là cài đặt tiêu chuẩn.

  • Hàng đợi là cấu trúc đằng sau BFS (tìm kiếm theo chiều rộng, chương 14 tệp 4), lập lịch tác vụ, và truyền thông điệp.

Dễ: Cài đặt Hàng đợi dùng Ngăn xếp

  • Bài toán: cài đặt một hàng đợi chỉ dùng hai ngăn xếp.

  • Mẫu: dùng một ngăn xếp để đẩy (push) và một để bốc (pop). Khi ngăn xếp pop rỗng, chuyển toàn bộ phần tử từ ngăn xếp push sang (đảo ngược thứ tự).

class MyQueue:
    def __init__(self):
        self.push_stack = []
        self.pop_stack = []

    def push(self, x):
        self.push_stack.append(x)

    def pop(self):
        if not self.pop_stack:
            while self.push_stack:
                self.pop_stack.append(self.push_stack.pop())
        return self.pop_stack.pop()

    def peek(self):
        if not self.pop_stack:
            while self.push_stack:
                self.pop_stack.append(self.push_stack.pop())
        return self.pop_stack[-1]

    def empty(self):
        return not self.push_stack and not self.pop_stack
  • Phân bổ \(O(1)\) mỗi thao tác: mỗi phần tử được di chuyển giữa các ngăn xếp nhiều nhất một lần.

Hàng đợi Ưu tiên và Heaps

  • Một hàng đợi ưu tiên (priority queue) trả về phần tử nhỏ nhất (hoặc lớn nhất) trước, bất kể thứ tự chèn. Cài đặt chuẩn là một đống nhị phân (binary heap).

  • Một min-heap là một cây nhị phân hoàn chỉnh nơi mọi cha đều nhỏ hơn các con của nó. Giá trị nhỏ nhất luôn ở gốc. Được lưu như một mảng: các con của node \(i\) ở vị trí \(2i + 1\) và \(2i + 2\).

Thao tác Thời gian
Chèn \(O(\log n)\)
Lấy min \(O(1)\)
Lấy và xóa min \(O(\log n)\)
Xây heap từ mảng \(O(n)\)
  • Mô-đun heapq của Python cung cấp min-heap. Để có max-heap, phủ định các giá trị.
import heapq

# Min-heap
h = []
heapq.heappush(h, 5)
heapq.heappush(h, 2)
heapq.heappush(h, 8)
print(heapq.heappop(h))  # 2 (nhỏ nhất)

# Mẹo Max-heap: phủ định giá trị
heapq.heappush(h, -10)
print(-heapq.heappop(h))  # 10 (lớn nhất)

Trung bình: Phần tử Lớn thứ K trong Mảng

  • Bài toán: tìm phần tử lớn thứ k.

  • Mẫu: duy trì một min-heap kích thước \(k\). Gốc của heap là phần tử lớn thứ k. Nếu heap có \(k\) phần tử và một phần tử mới lớn hơn gốc, thay thế gốc.

import heapq

def find_kth_largest(nums, k):
    heap = nums[:k]
    heapq.heapify(heap)  # O(k)

    for num in nums[k:]:
        if num > heap[0]:
            heapq.heapreplace(heap, num)  # pop min, push num: O(log k)

    return heap[0]

  • \(O(n \log k)\) thời gian, \(O(k)\) không gian. Tốt hơn nhiều so với sắp xếp (\(O(n \log n)\)) khi \(k \ll n\).

  • Cạm bẫy: dùng max-heap kích thước \(n\) và bốc \(k\) lần cũng hoạt động nhưng chậm hơn: \(O(n + k \log n)\). Min-heap kích thước \(k\) là phương pháp tối ưu.

Khó: Trộn K Danh sách Đã Sắp xếp

  • Bài toán: trộn \(k\) danh sách liên kết đã sắp xếp thành một danh sách đã sắp xếp.

  • Mẫu: dùng một min-heap chứa đầu của mỗi danh sách. Bốc phần tử nhỏ nhất, thêm nó vào kết quả, và đẩy node tiếp theo của nó lên heap.

import heapq

def merge_k_lists(lists):
    heap = []
    for i, lst in enumerate(lists):
        if lst:
            heapq.heappush(heap, (lst.val, i, lst))

    dummy = ListNode(0)
    curr = dummy

    while heap:
        val, i, node = heapq.heappop(heap)
        curr.next = node
        curr = curr.next
        if node.next:
            heapq.heappush(heap, (node.next.val, i, node.next))

    return dummy.next

  • \(O(n \log k)\) với \(n\) là tổng số node. Heap luôn có nhiều nhất \(k\) phần tử.

  • Cạm bẫy: chỉ số i (index) trong tuple heap là một bộ phá vỡ hòa (tiebreaker). Thiếu nó, Python sẽ cố so sánh các đối tượng ListNode khi các giá trị bằng nhau, gây crash vì ListNode không hỗ trợ <. Chỉ số đảm bảo một so sánh hợp lệ.

Tóm tắt các Cạm bẫy Thường gặp

Cạm bẫy Ví dụ Sửa
Null pointer trên fast.next Phát hiện vòng với while fast.next Kiểm tra fast and fast.next
Không xử lý danh sách rỗng Đảo ngược None Thêm guard if not head
Tràn ngăn xếp (underflow) Bốc từ ngăn xếp rỗng Kiểm tra len(stack) > 0 hoặc if stack
Quên sentinel Histogram bỏ sót các cột cuối Thêm 0 để xả ngăn xếp
Thiếu tiebreaker trong heap So sánh các đối tượng không thể so sánh Thêm chỉ số vào tuple heap
Sửa đổi danh sách khi đang duyệt Xóa node trong khi duyệt Dùng khuôn mẫu prev/curr hoặc đầu giả

Bài tập Tự luyện (NeetCode)

Danh sách liên kết

Ngăn xếp

Heaps / Hàng đợi Ưu tiên