Làm thế nào để kiểm tra xem một Danh sách liên kết đơn có cấu trúc đối xứng (Palindrome Linked List) hay không với độ phức tạp không gian tối ưu?

Question

Accepted Answer

Bản chất vấn đề
Một danh sách liên kết đối xứng có các giá trị đọc từ trái sang phải giống hệt như đọc từ phải sang trái. Thách thức cho Junior là danh sách liên kết đơn không hỗ trợ duyệt ngược lại từ đuôi về đầu như mảng (Array).
Giải pháp tối ưu

Sử dụng kỹ thuật Fast and Slow Pointers để tìm node nằm ở chính giữa danh sách.
Đảo ngược nửa sau của danh sách liên kết.
So sánh từng node của nửa đầu và nửa sau được đảo ngược.
(Tùy chọn) Khôi phục lại trạng thái ban đầu của danh sách để đảm bảo tính toàn vẹn dữ liệu (Side-effect free).

Ví dụ mã nguồn minh họa
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def isPalindrome(head: ListNode) -> bool:
    if not head or not head.next:
        return True

# Tìm giữa danh sách
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

# Đảo ngược nửa sau
    prev = None
    while slow:
        temp = slow.next
        slow.next = prev
        prev = slow
        slow = temp

# So sánh nửa đầu và nửa sau
    left, right = head, prev
    while right:
        if left.val != right.val:
            return False
        left = left.next
        right = right.next

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

Độ phức tạp thời gian (Time Complexity): O(N) vì ta duyệt qua danh sách một số lần hằng số.
Độ phức tạp không gian (Space Complexity): O(1) do thao tác trực tiếp trên các con trỏ hiện có mà không dùng thêm cấu trúc dữ liệu lưu trữ trung gian.

Kinh nghiệm thực chiến
Trong các hệ thống phân tán hoặc xử lý chuỗi ký tự dạng linked list, việc giữ nguyên trạng thái dữ liệu (Restoring list state) sau khi thuật toán chạy xong là một tiêu chuẩn coding standard cao cấp.

Làm thế nào để kiểm tra xem một Danh sách liên kết đơn có cấu trúc đối xứng (Palindrome Linked List) hay không với độ phức tạp không gian tối ưu?

Bản chất vấ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ủ đề