หาคู่ที่มีผลรวมกำหนดใน Doubly Linked List ด้วย C++

ภาพรวมปัญหา

ในปัญหานี้ เราจะได้รับ Doubly Linked List และค่าผลรวม (sum) งานของเราคือการหาคู่ของโหนดที่มีผลรวมของข้อมูลเท่ากับค่าที่กำหนด

ตัวอย่าง

อินพุต

head – 2 <-> 5 <-> 6 <-> 9 <-> 12  x = 11

เอาต์พุต

(2, 9), (5, 6)

คำอธิบาย

คู่ (2, 9) ผลรวม = 11
คู่ (5, 6) ผลรวม = 11

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

มี 2 วิธีหลักในการแก้ปัญหานี้:

วิธีที่ 1: Nested Loop (Brute Force) - O(n²)

วิธีง่ายที่สุดคือวนลูปผ่านทุกโหนด และสำหรับแต่ละโหนด ให้ค้นหาโหนดที่เหลือว่ามีคู่ที่รวมกันได้ sum หรือไม่ โดยใช้ nested loops

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

#include <iostream>
using namespace std;

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

void findSumPairs(struct Node *head, int sum) {
    struct Node *first = head;
    int pairCount = 0;
    while (first != NULL) {
        struct Node *second = first->next;
        while (second != NULL) {
            if ((first->data + second->data) == sum) {
                pairCount++;
                cout << "(" << first->data << ", " << second->data << ")\n";
            }
            second = second->next;
        }
        first = first->next;
    }
    if (!pairCount)
        cout << "No Such Pairs found !";
}

void insert(struct Node **head, int data) {
    struct Node *temp = new Node;
    temp->data = data;
    temp->next = temp->prev = NULL;
    if (!(*head))
        (*head) = temp;
    else {
        temp->next = *head;
        (*head)->prev = temp;
        (*head) = temp;
    }
}

int main() {
    struct Node *head = NULL;
    insert(&head, 12);
    insert(&head, 9);
    insert(&head, 6);
    insert(&head, 5);
    insert(&head, 2);
    int sum = 11;
    cout << "Pair in the linked list with sum = " << sum << " :\n";
    findSumPairs(head, sum);
    return 0;
}

วิธีที่ 2: Two Pointer Technique (ขั้นสูงกว่า) - O(n)

เนื่องจาก Linked List ถูกจัดเรียงแล้ว (Sorted) เราสามารถใช้ Two Pointers ได้:

• start ชี้ที่หัว (head) ของ Linked List
• end ชี้ที่ท้าย (last node) ของ Linked List

จากนั้นคำนวณผลรวม (sumVal) ของค่าทั้งสองโหนด:

• ถ้า sumVal > sum → เลื่อน end ไปทางซ้าย (end = end->prev)
• ถ้า sumVal < sum → เลื่อน start ไปทางขวา (start = start->next)
• ถ้า sumVal == sum → พิมพ์คู่, เลื่อน start ขวา และ end ซ้าย

หยุดเมื่อ pointer ทับกัน

โค้ดตัวอย่าง (Two Pointer)

#include <iostream>
using namespace std;

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

void findSumPairs(struct Node *head, int sum) {
    struct Node *start = head;
    struct Node *end = head;
    while (end->next != NULL)
        end = end->next;
    
    int pairCount = 0;
    while (start != NULL && end != NULL && start != end && end->next != start) {
        if ((start->data + end->data) == sum) {
            pairCount++;
            cout << "(" << start->data << ", " << end->data << ")\n";
            start = start->next;
            end = end->prev;
        }
        else if ((start->data + end->data) < sum)
            start = start->next;
        else
            end = end->prev;
    }
    if (!pairCount)
        cout << "No Such Pairs found !";
}

void insert(struct Node **head, int data) {
    struct Node *temp = new Node;
    temp->data = data;
    temp->next = temp->prev = NULL;
    if (!(*head))
        (*head) = temp;
    else {
        temp->next = *head;
        (*head)->prev = temp;
        (*head) = temp;
    }
}

int main() {
    struct Node *head = NULL;
    insert(&head, 12);
    insert(&head, 9);
    insert(&head, 6);
    insert(&head, 5);
    insert(&head, 2);
    int sum = 11;
    cout << "Pair in the linked list with sum = " << sum << " :\n";
    findSumPairs(head, sum);
    return 0;
}

เอาต์พุต

Pair in the linked list with sum = 11 : (2, 9) (5, 6)

สรุป

วิธี Two Pointer มีประสิทธิภาพมากกว่า เนื่องจากใช้เวลา O(n) ในขณะที่ Nested Loop ใช้ O(n²) เหมาะสำหรับ Linked List ที่มีขนาดใหญ่และจัดเรียงแล้ว