ตรวจสอบคู่ที่ให้ผลคูณเท่ากับ K ใน Linked List C++

ปัญหา

ให้ Linked List และค่า K ตรวจสอบว่ามีคู่ของโหนด (x, y) ที่ x × y = K หรือไม่

ตัวอย่าง: List = {2, 4, 8, 12, 15}, K = 16 → คู่ (2, 8)

วิธีแก้ปัญหา: Hashing

1. สร้าง Hash Set (unordered_set) เก็บค่าที่ผ่านมาแล้ว
2. ท่อง Linked List ทีละโหนด:
   • ค่าปัจจุบัน = curr
   • ถ้า K % curr == 0 และ (K/curr) อยู่ใน hash set → พบคู่แล้ว
   • เพิ่ม curr ลงใน hash set
3. ถ้าจบลูปไม่พบ → ไม่มีคู่

ความซับซ้อน: O(N) เวลา, O(N) พื้นที่

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

#include <iostream>
#include <unordered_set>
using namespace std;

struct Node {
    int data;
    Node* next;
};

void append(Node** head, int key) {
    Node* newNode = new Node{key, *head};
    *head = newNode;
}

bool isPairPresent(Node* head, int K) {
    unordered_set<int> seen;
    Node* curr = head;
    
    while (curr != nullptr) {
        int val = curr->data;
        
        // ตรวจสอบว่า K หาร val ลงตัว และคู่อยู่ใน set แล้ว
        if (val != 0 && K % val == 0 && seen.count(K / val)) {
            cout << "Pair found: (" << val << ", " << K/val << ")" << endl;
            return true;
        }
        
        seen.insert(val);
        curr = curr->next;
    }
    return false;
}

int main() {
    Node* head = nullptr;
    int arr[] = {2, 4, 8, 12, 15};
    int n = sizeof(arr)/sizeof(arr[0]);
    
    // สร้าง list (จะได้ลำดับย้อนกลับ: 15, 12, 8, 4, 2)
    for (int i = 0; i < n; i++)
        append(&head, arr[i]);
    
    int K = 16;
    if (!isPairPresent(head, K))
        cout << "NO PAIR EXIST" << endl;
    
    return 0;
}

ผลลัพธ์

Pair found: (2, 8)

กรณีพิเศษที่ต้องระวัง

• K = 0: ต้องมี 0 อยู่ใน list อย่างน้อย 2 ตัว (0×0=0) หรือ 0 และตัวอื่น
• ค่าซ้ำ: Hash set จัดการได้อัตโนมัติ (เก็บ unique values)
• Negative numbers: ทำงานได้ปกติ (เช่น K=6, คู่ (-2, -3))

โค้ดรองรับ K=0 และ negative

bool isPairPresentRobust(Node* head, int K) {
    unordered_set<int> seen;
    Node* curr = head;
    int zeroCount = 0;
    
    while (curr) {
        int val = curr->data;
        
        if (K == 0) {
            if (val == 0) {
                if (zeroCount > 0 || seen.count(0)) {
                    cout << "Pair: (0, 0)" << endl;
                    return true;
                }
                zeroCount++;
            } else if (seen.count(0)) {
                cout << "Pair: (" << val << ", 0)" << endl;
                return true;
            }
        } else if (val != 0 && K % val == 0 && seen.count(K / val)) {
            cout << "Pair: (" << val << ", " << K/val << ")" << endl;
            return true;
        }
        
        seen.insert(val);
        curr = curr->next;
    }
    return false;
}