Intersection of Two Linked Lists

+10

Hai danh sách liên kết đơn nằm trong cùng một nhóm nút. Nút i liên kết với nút next[i], còn -1 đánh dấu điểm kết thúc danh sách. Danh sách A bắt đầu tại nút headA, còn danh sách B bắt đầu tại nút headB. Các nút không được lưu theo thứ tự cụ thể nào, vì vậy hãy lần theo các liên kết.

Hai danh sách có thể nhập vào nhau: từ một nút nào đó trở đi, chúng tiếp tục đi qua cùng những nút cho đến cuối. Hãy trả về chỉ số của nút đầu tiên có mặt trong cả hai danh sách, hoặc -1 nếu chúng không có nút chung.

Hàm

getIntersectionNode(next: integer-array, headA: integer, headB: integer) → integer

nextinteger-array: chỉ số của nút mà mỗi nút liên kết đến, hoặc -1 nếu đó là nút cuối cùng trong danh sách
headAinteger: nút đầu tiên của danh sách A
headBinteger: nút đầu tiên của danh sách B
Trả vềinteger: nút đầu tiên mà cả hai danh sách cùng có, hoặc -1

Ràng buộc

2 ≤ n ≤ 10⁴, trong đó n là độ dài của next.
Mỗi next[i] là -1 hoặc chỉ số nút từ 0 đến n-1.
0 ≤ headA, headB ≤ n-1 và headA ≠ headB.
Cả hai danh sách đều kết thúc ở -1 mà không đi qua một nút nào hai lần. Không có chu trình.
Mỗi nút thuộc danh sách A, danh sách B hoặc cả hai.

Ví dụ

Đầu vào: next = [-1, 4, 1, 5, 0, 1]headA = 3headB = 2
Đầu ra: 1
Giải thích: A đi qua 3, 5, 1, 4, 0 và B đi qua 2, 1, 4, 0. Từ nút 1 trở đi, hai đường đi có chung mọi nút, và không có nút nào trước đó của A nằm trên đường đi của B, nên đáp án là 1.

Đầu vào: next = [2, 3, 4, -1, -1]headA = 0headB = 1
Đầu ra: -1
Giải thích: Danh sách A là 0, 2, 4 và danh sách B là 1, 3. Cả hai đều kết thúc ở -1 mà không chạm vào nút chung nào, nên đáp án là -1.

Đầu vào: next = [3, 2, 0, -1]headA = 1headB = 0
Đầu ra: 0
Giải thích: Danh sách A là 1, 2, 0, 3 và danh sách B là 0, 3. Danh sách B là phần đuôi của danh sách A, nên nút chung đầu tiên chính là headB, nút 0.

Câu hỏi mở rộng

Bạn có thể tìm nút trong thời gian O(m + k) với bộ nhớ phụ O(1) không?

Gợi ý

Mở từng gợi ý một. Mỗi gợi ý tiết lộ thêm một chút.

Đã mở 0/3

Lời giải

Một nút có một next, nên hai danh sách đã gặp nhau thì không bao giờ tách ra nữa. Chúng tạo thành hình chữ Y, với hai nhánh riêng nối vào một đuôi chung, và đáp án là điểm nối. Hai nhánh có thể dài khác nhau, nên cho hai danh sách tiến cùng lúc sẽ bỏ lỡ điểm nối. Ở dưới, m và k là độ dài của A và B.

Kiểm tra từng nút của A với tất cả các nút của B

Đúng, nhưng không chạy xong với các test lớn nhất

Ý tưởng

Con trỏ là chỉ số nút, và để tiến lên, ta dùng node = next[node]. Với mỗi nút a của A theo đúng thứ tự, hãy duyệt qua toàn bộ B và so sánh từng nút với a. Nút a đầu tiên khớp là đáp án, vì mọi nút trước đó của A đều không khớp. Cách này quét lại B cho mỗi nút của A: với 5000 nút trong mỗi danh sách và không có nút chung, ta cần 2.5 × 10^7 phép so sánh.

Thuật toán

Gán a = headA.
Khi a khác -1, duyệt b từ headB đến -1.
Nếu tại bất kỳ thời điểm nào b == a, trả về a.
Nếu không, chuyển a = next[a] rồi lặp lại.
Nếu danh sách A hết phần tử, trả về -1.

def getIntersectionNode(next, headA, headB):
    a = headA
    while a != -1:
        # Is node a also on list B? Walk all of B to find out.
        b = headB
        while b != -1:
            if a == b:
                return a
            b = next[b]
        a = next[a]
    return -1

Đánh dấu các nút của danh sách B

Ý tưởng

Trả lời câu hỏi “nút này có nằm trên B không?” một lần cho mỗi nút: duyệt B và đánh dấu từng nút trong một mảng boolean có kích thước n. Chỉ số nút là các số nguyên nhỏ, nên dùng mảng thay cho tập hợp băm là đủ. Sau đó, duyệt A từ nút đầu. Nút đầu tiên được đánh dấu nằm trong cả hai danh sách, và đây là nút đầu tiên như vậy vì bạn duyệt A theo thứ tự. Trong ví dụ đầu tiên, B đánh dấu 2, 1, 4, 0, và lượt duyệt A đi qua 3 và 5 trước khi dừng ở 1. Mỗi danh sách chỉ được duyệt một lần, nên độ phức tạp thời gian là O(m + k), đổi lại cần n dấu đánh dấu.

Thuật toán

Tạo onB, một mảng gồm n giá trị boolean được đặt thành false.
Duyệt danh sách B bắt đầu từ headB và đặt onB[node] = true cho mỗi nút.
Duyệt danh sách A bắt đầu từ headA. Trả về nút đầu tiên có onB[node] là true.
Nếu danh sách A kết thúc, trả về -1.

def getIntersectionNode(next, headA, headB):
    # Mark every node of list B.
    on_b = [False] * len(next)
    node = headB
    while node != -1:
        on_b[node] = True
        node = next[node]
    # The first marked node on list A is the meeting point.
    node = headA
    while node != -1:
        if on_b[node]:
            return node
        node = next[node]
    return -1

Hai con trỏ chuyển đổi danh sách

Ý tưởng

Chia mỗi danh sách tại điểm nối: A có x nút riêng rồi đến c nút chung, còn B có y nút riêng rồi đến cùng c nút đó. Con trỏ a đi qua A, bước đến -1, rồi bắt đầu lại từ headB và lần thứ hai đến điểm nối sau x + c + 1 + y bước. Con trỏ b đi qua B rồi đến A, và tới nơi sau y + c + 1 + x bước. Tổng số bước bằng nhau. Ở ví dụ đầu tiên, x = 2, y = 1 và c = 3, cả hai đều đứng tại nút 1 sau bảy bước.

Nếu không có phần đuôi chung, cả hai con trỏ đều đứng tại -1 sau m + 1 + k bước (sau m bước khi m = k), và vòng lặp trả về -1. Điểm dừng chung đó là lý do mỗi con trỏ bước đến -1 trước khi chuyển hướng. Mỗi con trỏ di chuyển nhiều nhất m + k + 1 lần, với bộ nhớ gồm hai chỉ số.

Thuật toán

Gán a = headA và b = headB.
Khi a != b: chuyển a đến headB nếu nó là -1, nếu không thì chuyển đến next[a].
Trong cùng vòng lặp, chuyển b đến headA nếu nó là -1, nếu không thì chuyển đến next[b].
Khi vòng lặp kết thúc, trả về a. Đó là nút chung đầu tiên hoặc -1.

def getIntersectionNode(next, headA, headB):
    a, b = headA, headB
    # Each pointer walks its own list, then the other one. Both cover
    # the same number of nodes, so they reach the meeting node together,
    # or reach -1 together when there is none.
    while a != b:
        a = headB if a == -1 else next[a]
        b = headA if b == -1 else next[b]
    return a

Lỗi thường gặp và trường hợp biên

Chuyển thẳng từ nút cuối sang đầu danh sách kia, bỏ qua điểm dừng tại -1. Khi hai danh sách không có nút chung, các con trỏ không bao giờ có cùng giá trị và vòng lặp chạy mãi.
Đặt lại con trỏ ở đầu danh sách của chính nó. Mỗi con trỏ sẽ đi vòng quanh danh sách riêng, và chúng chỉ gặp nhau khi số vòng đi trùng khớp, việc này có thể cần đến (m + 1)·(k + 1) bước di chuyển.
Coi thứ tự trong mảng là thứ tự trong danh sách. Nút 0 chỉ là nút đầu nếu headA hoặc headB chỉ định như vậy, và các phần tử liền kề trong mảng không phải là các nút liền kề trong danh sách.
Trong Lua và R, đừng quên rằng mảng bắt đầu từ 1. Giữ chỉ số nút bắt đầu từ 0 và đọc next[node + 1].

Câu hỏi thường gặp3

Làm thế nào để tìm điểm giao nhau của hai danh sách liên kết mà không cần thêm bộ nhớ?

Chạy hai con trỏ. Mỗi con trỏ đi qua danh sách riêng của mình, rồi sau khi đi hết danh sách thì tiếp tục từ đầu danh sách còn lại. Cả hai đi cùng một quãng đường, nên chúng đến nút chung đầu tiên cùng lúc, hoặc cùng đi đến cuối nếu không có nút chung nào.

Bạn có thể tìm phần giao nhau bằng cách so sánh độ dài của các danh sách không?

Có. Hãy đếm số nút của cả hai danh sách, đưa con trỏ trên danh sách dài hơn tiến lên trước một khoảng bằng độ chênh lệch, rồi mỗi lần di chuyển cả hai một bước cho đến khi chúng bằng nhau. Cách này cũng mất thời gian O(m + k) và dùng bộ nhớ O(1); phương pháp chuyển đổi giúp căn chỉnh tương tự mà không cần hai lượt đếm.

Độ phức tạp thời gian khi tìm phần giao của hai danh sách liên kết là bao nhiêu?

Hai phương thức dùng hai con trỏ và độ dài chạy trong thời gian O(m + k) với bộ nhớ bổ sung O(1). Lưu một danh sách vào tập hợp hoặc mảng đánh dấu cũng có độ phức tạp tuyến tính, nhưng cần bộ nhớ cho danh sách đó. So sánh mọi cặp nút cần thời gian O(m·k).

def getIntersectionNode(next, headA, headB):
    # Viết code ở đây

Kiểm thử #1

Kiểm thử #2

Kiểm thử #3

Đối số

next = [-1, 4, 1, 5, 0, 1]
headA = 3
headB = 2

Đầu ra mong đợi

Intersection of Two Linked Lists

Hàm

Ràng buộc

Ví dụ

Gợi ý

Lời giải

Kiểm tra từng nút của A với tất cả các nút của B

Đánh dấu các nút của danh sách B

Hai con trỏ chuyển đổi danh sách

Lỗi thường gặp và trường hợp biên

Câu hỏi thường gặp3

Bài tập tương tự