Tìm điểm giao nhau của hai danh sách liên kết trong Java

Danh sách liên kết (Linked List) là cấu trúc dữ liệu tuyến tính, mỗi node có 2 khối: giá trị dữ liệu và địa chỉ node tiếp theo.

Giả sử hai danh sách liên kết có con trỏ ngẫu nhiên trỏ đến các node khác nhau. Nhiệm vụ: tìm node giao nhau của hai danh sách. Nếu không giao nhau, trả về NULL.

Ví dụ

Input-1: Hai danh sách giao nhau tại node giá trị '2'

Output: 2

Giải thích: Danh sách giao nhau tại node giá trị 2 → trả về 2.

Input-2: Hai danh sách không có điểm chung

Output: NULL

Giải thích: Không có điểm chung → trả về NULL.

Phương pháp giải quyết

• Hai danh sách có điểm chung. Duyệt cả hai cho đến khi trỏ đến cùng giá trị.
• Hàm commonPoint(listnode* headA, listnode* headB) trả về giá trị điểm chung
• Hàm count() tính độ dài danh sách
• Tạo con trỏ p1, p2 trỏ headA, headB
• Duyệt danh sách dài hơn trước (chênh lệch độ dài)
• Sau đó duyệt cùng lúc cho đến khi p1.data == p2.data
• Trả về giá trị node giao nhau

Ví dụ mã Java

public class Solution {
    static listnode headA, headB;
    
    static class listnode {
        int data;
        listnode next;
        listnode(int d) {
            data = d;
            next = null;
        }
    }
    
    int count(listnode head) {
        int c = 0;
        while (head != null) {
            c++;
            head = head.next;
        }
        return c;
    }
    
    int commonPoint(listnode headA, listnode headB) {
        listnode p1 = headA;
        listnode p2 = headB;
        int c1 = count(headA);
        int c2 = count(headB);
        
        if (c1 > c2) {
            for (int i = 0; i < c1 - c2; i++) {
                if (p1 == null) return -1;
                p1 = p1.next;
            }
        }
        if (c1 < c2) {
            for (int i = 0; i < c2 - c1; i++) {
                if (p2 == null) return -1;
                p2 = p2.next;
            }
        }
        
        while (p1 != null && p2 != null) {
            if (p1.data == p2.data) {
                return p1.data;
            }
            p1 = p1.next;
            p2 = p2.next;
        }
        return -1;
    }
    
    public static void main(String[] args) {
        Solution list = new Solution();
        list.headA = new listnode(5);
        list.headA.next = new listnode(4);
        list.headA.next.next = new listnode(9);
        list.headA.next.next.next = new listnode(7);
        list.headA.next.next.next.next = new listnode(1);
        list.headB = new listnode(6);
        list.headB.next = new listnode(7);
        list.headB.next.next = new listnode(1);
        System.out.println(list.commonPoint(headA, headB));
    }
}

Đầu ra

7

Giải thích: Hai danh sách giao nhau tại node giá trị 7.