Giao điểm của 2 Linked List trong C++

Cho 2 Linked List, tìm node giao điểm (intersection). Nếu không giao → NULL.

Ví dụ

Input 1:

Output: 2 (giao tại node giá trị 2)

Input 2:

Output: NULL

Cách tiếp cận

• Tính độ dài 2 list
• Con trỏ p1, p2 trỏ headA, headB
• Dịch con trỏ list dài hơn chênh lệch độ dài
• Duyệt song song cho đến khi p1 == p2
• Trả về giá trị node giao điểm

Code C++

#include <bits/stdc++.h>
using namespace std;

class listnode {
public:
    int data;
    listnode* next;
};

int count(listnode* head) {
    int cnt = 0;
    while (head) { cnt++; head = head->next; }
    return cnt;
}

int commonPoint(listnode* headA, listnode* headB) {
    int len1 = count(headA), len2 = count(headB);
    listnode *p1 = headA, *p2 = headB;
    if (len1 > len2) for (int i=0; inext;
    if (len2 > len1) for (int i=0; inext;
    while (p1 && p2) {
        if (p1 == p2) return p1->data;
        p1 = p1->next; p2 = p2->next;
    }
    return -1;
}

int main() {
    listnode *headA = new listnode(); headA->data = 5;
    listnode *headB = new listnode(); headB->data = 4;
    listnode *head = new listnode(); head->data = 9; headB->next = head;
    head = new listnode(); head->data = 2; headB->next->next = head;
    head = new listnode(); head->data = 7; headA->next = head; headB->next->next->next = head;
    head = new listnode(); head->data = 3; headA->next->next = head; headA->next->next->next = NULL;
    cout << commonPoint(headA, headB) << endl;
}

Kết quả

7

2 list giao nhau tại node giá trị 7.