Làm thế nào để tìm node giao nhau (Intersection Node) của hai Danh sách liên kết đơn trong môi trường có ràng buộc nghiêm ngặt về bộ nhớ?

Question

Accepted Answer

Bản chất vấn đề
Khi hai danh sách liên kết đơn hội tụ tại một điểm, chúng sẽ chia sẻ chung tất cả các node từ điểm giao nhau đó cho đến hết danh sách. Thách thức đặt ra là tìm ra chính xác node bắt đầu giao nhau mà không làm thay đổi cấu trúc dữ liệu và không dùng cấu trúc phụ trợ như Hash Set.
Giải pháp tối ưu
Sử dụng thuật toán hai con trỏ (Two Pointers). Cho hai con trỏ xuất phát từ hai node đầu tiên của hai danh sách. Khi một con trỏ chạy hết danh sách của nó, ta chuyển nó sang đầu danh sách còn lại. Bằng cách này, quãng đường di chuyển của cả hai con trỏ sẽ bằng nhau (Length A + Length B), giúp chúng gặp nhau đúng tại node giao nhau hoặc tại giá trị null nếu không có giao điểm.
Ví dụ mã nguồn minh họa
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

def getIntersectionNode(headA: ListNode, headB: ListNode) -> ListNode:
    if not headA or not headB:
        return None

pointerA = headA
    pointerB = headB

while pointerA != pointerB:
        # Chuyển sang danh sách còn lại khi đi hết
        pointerA = pointerA.next if pointerA else headB
        pointerB = pointerB.next if pointerB else headA

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

Độ phức tạp thời gian (Time Complexity): O(N + M) với N và M là độ dài của hai danh sách.
Độ phức tạp không gian (Space Complexity): O(1) vì không sử dụng thêm Hash Map hay mảng phụ trợ nào.

Kinh nghiệm thực chiến
Đây là câu hỏi yêu cầu ứng viên cấp độ Junior thể hiện tư duy tối ưu không gian bộ nhớ (Space Optimization), một kỹ năng cực kỳ quan trọng khi xây dựng các ứng dụng chạy trên thiết bị phần cứng hạn chế tài nguyên.

Làm thế nào để tìm node giao nhau (Intersection Node) của hai Danh sách liên kết đơn trong môi trường có ràng buộc nghiêm ngặt về bộ nhớ?

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ủ đề