Làm thế nào để phân vùng một Danh sách liên kết đơn sao cho tất cả các node có giá trị nhỏ hơn một giá trị x xuất hiện trước các node có giá trị lớn hơn hoặc bằng x (Partition List)?

Question

Accepted Answer

Bản chất bài toán
Cho một Linked List và một giá trị x, bạn cần sắp xếp lại các node sao cho thứ tự tương đối của các node trong mỗi phân vùng được giữ nguyên. Đây là bài toán thường gặp khi cần lọc hoặc nhóm dữ liệu trong các bộ đệm (Buffers) hoặc hàng đợi ưu tiên (Priority Queues).
Thuật toán giải quyết
Thay vì cố gắng hoán đổi giá trị bên trong các node (có thể vi phạm tính đóng gói hoặc gây tốn kém thời gian nếu dữ liệu phức tạp), chiến lược tối ưu là tách danh sách ban đầu thành hai danh sách liên kết tạm thời:

Danh sách thứ nhất chứa các node nhỏ hơn x (gọi là beforeList).
Danh sách thứ hai chứa các node lớn hơn hoặc bằng x (gọi là afterList).
Duyệt qua danh sách gốc, nối các node vào đúng danh sách tương ứng.
Sau khi duyệt xong, nối đuôi của beforeList với đầu của afterList.

Ví dụ mã nguồn minh họa (Python)
def partition(head: ListNode, x: int) -> ListNode:
    before_head = ListNode(0)
    before = before_head
    after_head = ListNode(0)
    after = after_head

current = head
    while current:
        if current.val < x:
            before.next = current
            before = before.next
        else:
            after.next = current
            after = after.next
        current = current.next

after.next = None
    before.next = after_head.next

return before_head.next
Độ phức tạp

Thời gian (Time Complexity): O(N) với N là tổng số node trong danh sách do chỉ duyệt qua đúng một lần.
Không gian (Space Complexity): O(1) vì chỉ sử dụng lại các con trỏ hiện có mà không cấp phát thêm bộ nhớ cho node mới.

Lưu ý thực chiến Enterprise
Luôn nhớ ngắt kết nối (after.next = None) ở cuối danh sách thứ hai để tránh tạo ra các vòng lặp vô hạn (Cycles) trong cấu trúc dữ liệu, điều này rất quan trọng trong các ứng dụng đa luồng (Multithreading) khi dữ liệu có thể bị đọc đồng thời.

Làm thế nào để phân vùng một Danh sách liên kết đơn sao cho tất cả các node có giá trị nhỏ hơn một giá trị x xuất hiện trước các node có giá trị lớn hơn hoặc bằng x (Partition List)?

Bản chất bài toán

Làm Chủ Phỏng Vấn & Nâng Cao Trình Độ Chuyên Nghiệp

Tải Tuyển Tập 100+ Câu Hỏi Phỏng Vấn Chuyên Sâu (PDF)

Cần Mentor Phỏng Vấn Thử 1-1 & Tối Ưu CV?

Kiểm Tra CV Chuẩn ATS Miễn Phí

Câu hỏi linked lists liên quan cùng chủ đề