หาคู่ที่ผลรวมเท่ากับค่ากำหนดใน Singly Linked List เรียงลำดับโดยไม่ใช้พื้นที่เพิ่มใน C++

สมมติเรามี singly linked list และค่า x เราต้องหาคู่ที่ผลรวมเท่ากับ x โดยไม่สามารถใช้พื้นที่เพิ่มเติม (extra space) ได้ และ time complexity คาดว่าจะเป็น O(n)

เช่น ถ้าอินพุตเป็น 4→7→8→9→10→11→12, x = 19 เอาต์พุตจะเป็น [(7, 12), (8, 11), (9, 10)]

ขั้นตอนการแก้:

• กำหนดฟังก์ชัน convert_to_xor() รับ start:

• prev := NULL

• while start != NULL:

  • next_list_node := next ของ start
  • next ของ start := XOR ของ address ของ next_list_node และ prev
  • prev := start
  • start := next_list_node

• ใน main:

  • first := start
  • next_list_node := NULL, prev := NULL, second := start
  • while next ของ second != prev:
    • temp := second
    • second := XOR(address of (next ของ second, prev))
    • prev := temp
  • next_list_node := NULL, prev := NULL, flag := false
  • while (first != NULL && second != NULL && first != second && first != next_list_node):
    • ถ้า data ของ first + data ของ second == x:
      • แสดงคู่ data ของ first, data ของ second
      • flag := true
      • เลื่อน first และ second ด้วย XOR
    • มิฉะนั้น:
      • ถ้า data ของ first + data ของ second < x: เลื่อน first ไปข้างหน้า
      • มิฉะนั้น: เลื่อน second ไปข้างหลัง
  • ถ้า flag == false: แสดง "No pair found"

ตัวอย่าง (C++)

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

class ListNode {
public:
    int data;
    ListNode *next;
    ListNode(int data) {
        this->data = data;
        next = NULL;
    }
};

ListNode *make_list(vector<int> v) {
    ListNode *start = new ListNode(v[0]);
    for (int i = 1; i < v.size(); i++) {
        ListNode *ptr = start;
        while (ptr->next != NULL) ptr = ptr->next;
        ptr->next = new ListNode(v[i]);
    }
    return start;
}

ListNode* XOR(ListNode *a, ListNode *b) {
    return (ListNode*) ((uintptr_t)(a) ^ (uintptr_t)(b));
}

void convert_to_xor(ListNode *start) {
    ListNode *next_list_node;
    ListNode *prev = NULL;
    while (start != NULL) {
        next_list_node = start->next;
        start->next = XOR(next_list_node, prev);
        prev = start;
        start = next_list_node;
    }
}

void get_pared_sum(ListNode *start, int x) {
    ListNode *first = start;
    ListNode *next_list_node = NULL, *prev = NULL;
    ListNode *second = start;
    while (second->next != prev) {
        ListNode *temp = second;
        second = XOR(second->next, prev);
        prev = temp;
    }
    next_list_node = NULL;
    prev = NULL;
    bool flag = false;
    while (first != NULL && second != NULL && first != second && first != next_list_node) {
        if ((first->data + second->data) == x) {
            cout << "(" << first->data << "," << second->data << ")" << endl;
            flag = true;
            ListNode *temp = first;
            first = XOR(first->next, prev);
            prev = temp;
            temp = second;
            second = XOR(second->next, next_list_node);
            next_list_node = temp;
        } else {
            if ((first->data + second->data) < x) {
                ListNode *temp = first;
                first = XOR(first->next, prev);
                prev = temp;
            } else {
                ListNode *temp = second;
                second = XOR(second->next, next_list_node);
                next_list_node = temp;
            }
        }
    }
    if (flag == false)
        cout << "No pair found" << endl;
}

int main() {
    vector<int> v = {4, 7, 8, 9, 10, 11, 12};
    ListNode* start = make_list(v);
    int x = 19;
    convert_to_xor(start);
    get_pared_sum(start, x);
}

อินพุต

{4, 7, 8, 9, 10, 11, 12}

เอาต์พุต

(7,12) (8,11) (9,10)