Tìm cặp có tổng cho trước trong danh sách liên kết đơn đã sắp xếp không dùng bộ nhớ thêm trong C++

Cho danh sách liên kết đơn (singly linked list) đã sắp xếp và giá trị x. Tìm cặp có tổng bằng x. Không dùng bộ nhớ thêm, độ phức tạp O(n).

Ví dụ: 4→7→8→9→10→11→12, x = 19 → [(7,12), (8,11), (9,10)]

Giải pháp dùng XOR Linked List

Chuyển danh sách liên kết đơn thành danh sách XOR (mỗi nút next lưu XOR của địa chỉ next và prev). Sau đó dùng hai con trỏ first (đầu) và second (cuối) di chuyển nhau bằng phép XOR để tìm cặp.

Các bước

• Hàm convert_to_xor(): duyệt list, next = XOR(next_node, prev).
• Khởi tạo first = head, second = cuối list (duyệt bằng XOR).
• Dùng hai con trỏ first, second di chuyển về nhau bằng XOR, so sánh tổng với x.
• Nếu tổng == x: in cặp, di chuyển cả hai.
• Nếu tổng < x: tiến first.
• Nếu tổng > x: lùi second.
• Dừng khi first == second hoặc first == next_node hoặc second == prev_node.

Ví dụ

#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_node, *prev = NULL;
    while (start != NULL) {
        next_node = start->next;
        start->next = XOR(next_node, prev);
        prev = start;
        start = next_node;
    }
}

void get_pared_sum(ListNode *start, int x) {
    ListNode *first = start;
    ListNode *next_node = NULL, *prev = NULL;
    ListNode *second = start;
    while (second->next != prev) {
        ListNode *temp = second;
        second = XOR(second->next, prev);
        prev = temp;
    }
    next_node = NULL;
    prev = NULL;
    bool flag = false;
    while (first != NULL && second != NULL && first != second && first != next_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_node);
            next_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_node);
                next_node = temp;
            }
        }
    }
    if (!flag) cout << "Không tìm thấy cặp" << 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);
}

Đầu ra

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