Intersection ของ Linked List 2 ตัวใน C++

โจทย์

หาจุดตัด (Intersection Node) ของ Singly Linked List 2 ตัว จุดตัด = โหนดเดียวกัน (Address เดียวกัน ไม่ใช่แค่ค่าเท่ากัน) ถ้าไม่ตัดกัน Return NULL

ตัวอย่าง

List A: 5 → 7 → 3
                ↘
                 9 → 2 → NULL
                ↗
List B:    4 → 6
Intersection: Node 9 (Value 9)

แนวคิด: Length Difference

1. หาความยาวทั้ง 2 List: lenA, lenB
2. ขยับ Pointer ของ List ที่ยาวกว่าไปก่อน |lenA - lenB| ก้าว
3. เดินพร้อมกันจนกว่า ptrA == ptrB (Address เท่ากัน)

โค้ด C++

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

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

int getLength(ListNode* head) {
    int len = 0;
    while (head) {
        len++;
        head = head->next;
    }
    return len;
}

ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
    int lenA = getLength(headA);
    int lenB = getLength(headB);
    
    ListNode* pA = headA;
    ListNode* pB = headB;
    
    // ขยับ pointer ยาวกว่า
    if (lenA > lenB) {
        for (int i = 0; i < lenA - lenB; i++) pA = pA->next;
    } else {
        for (int i = 0; i < lenB - lenA; i++) pB = pB->next;
    }
    
    // เดินพร้อมกันหาจุดตัด
    while (pA && pB) {
        if (pA == pB) return pA; // Address เท่ากัน
        pA = pA->next;
        pB = pB->next;
    }
    return nullptr;
}

// Two-Pointer Trick (ไม่ต้องนับความยาว)
ListNode* getIntersectionNode2(ListNode* headA, ListNode* headB) {
    ListNode* pA = headA;
    ListNode* pB = headB;
    
    while (pA != pB) {
        pA = pA ? pA->next : headB; // หมด A → เริ่ม B
        pB = pB ? pB->next : headA; // หมด B → เริ่ม A
    }
    return pA; // NULL หรือ Intersection
}

int main() {
    // สร้าง List ที่ตัดกันที่ Node 7
    ListNode* common = new ListNode(7);
    common->next = new ListNode(3);
    
    ListNode* headA = new ListNode(5);
    headA->next = common;
    
    ListNode* headB = new ListNode(4);
    headB->next = new ListNode(6);
    headB->next->next = common;
    
    ListNode* inter = getIntersectionNode(headA, headB);
    cout << "Intersection: " << (inter ? to_string(inter->val) : "NULL") << endl;
    
    // Test ไม่ตัดกัน
    ListNode* headC = new ListNode(1);
    headC->next = new ListNode(2);
    ListNode* headD = new ListNode(3);
    headD->next = new ListNode(4);
    
    cout << "No Intersection: " << (getIntersectionNode(headC, headD) ? "Found" : "NULL") << endl;
    
    return 0;
}

Two-Pointer Trick 解釋

Pointer A เดิน: A → (จบ) → B

Pointer B เดิน: B → (จบ) → A

ระยะทางรวมเท่ากัน: lenA + lenB จะพบกันที่ Intersection (หรือ NULL พร้อมกัน)

Complexity

• Time: O(m + n)
• Space: O(1)

ผลลัพธ์

Intersection: 7
No Intersection: NULL

สรุป

Intersection of Linked Lists แก้ได้ 2 วิธี: (1) นับความยาว + Align (2) Two-Pointer Trick (Eleganter) ทั้งคู่ O(m+n) Time, O(1) Space - LeetCode 160