หาจุดตัดของ Linked List สองตัวใน Java

ภาพรวมปัญหา

ได้รับ Linked List สองตัวที่อาจ intersect กัน (share โหนดเดียวกันจากจุดหนึ่งไปจนจบ) ต้องหาโหนดที่ intersect (common node) หากไม่ intersect คืนค่า NULL

ตัวอย่าง

Input 1

List A: 5 → 4 → 9 → 7 → 1
List B: 6 → 7 → 1

Output: 7 (จุดตัดที่โหนดค่า 7)

Input 2

ไม่มีจุดตัด

Output: NULL

แนวทางแก้ปัญหา (Two Pointers + Length Difference)

1. หาความยาวของทั้งสอง List (c1, c2)
2. ให้ pointer p1, p2 ชี้ที่ head ของแต่ละ List
3. ขยับ pointer ของ List ที่ยาวกว่าไปก่อน |c1 - c2| ก้าว
4. ขยับ p1, p2 ทีละก้าวพร้อมกัน จนกว่า p1 == p2 (เจอจุดตัด) หรือถึง null (ไม่มีจุดตัด)
5. คืนค่า data ของโหนดที่เจอ (หรือ -1/NULL)

ตัวอย่างโค้ด Java

public class Solution {
    static class ListNode {
        int data;
        ListNode next;
        ListNode(int d) { data = d; next = null; }
    }

    static ListNode headA, headB;

    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, p2 = headB;
        int c1 = count(headA), c2 = count(headB);

        if (c1 > c2) for (int i = 0; i < c1 - c2; i++) p1 = p1.next;
        else if (c2 > c1) for (int i = 0; i < c2 - c1; i++) p2 = p2.next;

        while (p1 != null && p2 != null) {
            if (p1.data == p2.data) return p1.data; // หรือเปรียบเทียบ reference p1 == p2
            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)); // 7
    }
}

ผลลัพธ์

7

หมายเหตุสำคัญ

ควรเปรียบเทียบ Reference (p1 == p2) ไม่ใช่ค่า data เพราะอาจมีค่าเท่ากันแต่เป็นโหนดคนละตัว