在C ++中以单链接形式查找给定总和的对,而没有多余空间

假设我们有一个单链表和一个值x;我们必须找到一个总和与x相同的对。我们必须记住,我们不能使用任何额外的空间,并且预期的时间复杂度将为O(n)。

因此,如果输入为4→7→8→9→10→11→12,x = 19,则输出将为[(7,12),(8,11),(9,10)]

为了解决这个问题,我们将遵循以下步骤-

  • 定义一个函数convert_to_xor(),这将开始,

  • 上一页:= NULL

  • 当start为NULL时,执行-

    • next_list_node:=开始的下一个

    • 下一个开始:= next_list_node和prev的地址的异或

    • 上一个:=开始

    • 开始:= next_list_node

  • 从主要方法中,执行以下操作-

  • 首先:=开始

  • next_list_node:= NULL,上一个:= NULL,第二个:=开始

  • 虽然下一秒不等于上一个,但是-

    • 温度:=秒

    • second:=地址的XOR(秒的下一个,上一个)

    • 上一页:=临时

  • next_list_node:= NULL

  • 上一页:= NULL

  • 标志:=假

  • while(第一个不等于NULL,第二个不等于NULL,第一个不等于second,第一个不等于next_list_node),-

    • 如果第一个数据+第二个数据<x,则

    • 除此以外

    • temp:=首先

    • first:=地址的XOR(first,prev的下一个)

    • 上一页:=临时

    • 温度:=秒

    • second:=地址的异或(秒数的下一个,next_list_node)

    • next_list_node:=临时

    • 显示第一对数据,第二对数据

    • 标志:= true

    • temp:=首先

    • first:=地址的XOR(first,prev的下一个)

    • 上一页:=临时

    • 温度:=秒

    • second:=第二个next,next_list_node的下一个地址的XOR)

    • next_list_node:=临时

    • 如果第一个数据+第二个数据与x相同,则-

    • 除此以外

    • 如果flag与false相同,则-

      • 没有一对

    范例(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)