在没有额外空间的排序单链接中查找给定和的对-yiteyi-C++库

给定一个排序的单链表和一个值x，任务是找到和等于x的对。我们不允许使用任何额外的空间，预期的时间复杂度为O（n）。

null

例如：

Input : head = 3-->6-->7-->8-->9-->10-->11 , x=17Output: (6, 11), (7, 10), (8, 9)

提示：我们可以修改原始链表

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

A. 简单解决方案 对于这个问题，需要一个接一个地获取每个元素，并向前遍历剩余的列表，以找到第二个元素，其和等于给定值x。这种方法的时间复杂度为O（n） ^2. ).

一 有效解决方案 因为这个问题是基于以下文章中讨论的想法。在双链接列表中查找配对：我们使用从两端遍历链表的相同算法。异或链表：在单链表中，我们只能向前遍历列表。我们使用XOR概念将单链表转换为双链表。

以下是步骤：

首先，我们需要将单链表转换为双链表。这里我们给出了单链表结构节点，它只有 下一个 指针不是上指针，所以要将单链表转换为我们使用的双链表高效内存的双链表（XOR链表） .
在XOR链表中 下一个 单链表的指针包含 下一个 和上指针。
在将单链表转换为双链表之后，我们初始化两个指针变量，以在已排序的双链表中找到候选元素。初始化第一以双链表开始，即； 第一个=头 初始化第二具有双链表的最后一个节点，即； 第二个=最后一个节点 .
这里我们没有随机访问，所以为了初始化指针，我们遍历列表直到最后一个节点，并将最后一个节点分配给第二个节点。
如果当前第一和第二小于x，我们就移动第一在前进方向。如果当前第一和第二元素大于x，然后我们移动第二在向后的方向。
循环终止条件也不同于阵列。当两个指针中的任何一个变为NULL，或者它们相互交叉（first=next_node），或者它们变得相同（first=second）时，循环终止。

C++

                         // C++ program to find pair with given sum in a singly                       
                         // linked list in O(n) time and no extra space.                       
                         #include<bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         /* Link list node */                       
                         struct                                     Node                       
                         {                       
                                                 int                                     data;                       
           
                                                 /* also contains XOR of next and                       
                                                 previous node after conversion*/                       
                                                 struct                                     Node* next;                       
                         };                       
           
                         /* Given a reference (pointer to pointer) to the head                       
                                                 of a list and an int, push a new node on the front                       
                                                 of the list. */                       
                         void                                     insert(                                     struct                                     Node** head_ref,                                     int                                     new_data)                       
                         {                       
                                                 /* allocate node */                       
                                                 struct                                     Node* new_node =                       
                                                 (                                     struct                                     Node*)                                     malloc                                     (                                     sizeof                                     (                                     struct                                     Node));                       
           
                                                 /* put in the data */                       
                                                 new_node->data = new_data;                       
           
                                                 /* link the old list off the new node */                       
                                                 new_node->next = (*head_ref);                       
           
                                                 /* move the head to point to the new node */                       
                                                 (*head_ref) = new_node;                       
                         }                       
           
                         /* returns XORed value of the node addresses */                       
                         struct                                     Node* XOR (                                     struct                                     Node *a,                                     struct                                     Node *b)                       
                         {                       
                                                 return                                     (                                     struct                                     Node*) ((                                     uintptr_t                                     ) (a) ^ (                                     uintptr_t                                     ) (b));                       
                         }                       
           
                         // Utility function to convert singly linked list                       
                         // into XOR doubly linked list                       
                         void                                     convert(                                     struct                                     Node *head)                       
                         {                       
                                                 // first we store address of next node in it                       
                                                 // then take XOR of next node and previous node                       
                                                 // and store it in next pointer                       
                                                 struct                                     Node *next_node;                       
           
                                                 // prev node stores the address of previously                       
                                                 // visited node                       
                                                 struct                                     Node *prev = NULL;                       
           
                                                 // traverse list and store xor of address of                       
                                                 // next_node and prev node in next pointer of node                       
                                                 while                                     (head != NULL)                       
                                                 {                       
                                                 // address of next node                       
                                                 next_node = head->next;                       
           
                                                 // xor of next_node and prev node                       
                                                 head->next = XOR(next_node, prev);                       
           
                                                 // update previous node                       
                                                 prev = head;                       
           
                                                 // move head forward                       
                                                 head = next_node;                       
                                                 }                       
                         }                       
           
                         // function to Find pair whose sum is equal to                       
                         // given value x                       
                         void                                     pairSum(                                     struct                                     Node *head,                                     int                                     x)                       
                         {                       
                                                 // initialize first                       
                                                 struct                                     Node *first = head;                       
           
                                                 // next_node and prev node to calculate xor again                       
                                                 // and find next and prev node while moving forward                       
                                                 // and backward direction from both the corners                       
                                                 struct                                     Node *next_node = NULL, *prev = NULL;                       
           
                                                 // traverse list to initialize second pointer                       
                                                 // here we need to move in forward direction so to                       
                                                 // calculate next address we have to take xor                       
                                                 // with prev pointer because (a^b)^b = a                       
                                                 struct                                     Node *second = head;                       
                                                 while                                     (second->next != prev)                       
                                                 {                       
                                                 struct                                     Node *temp = second;                       
                                                 second = XOR(second->next, prev);                       
                                                 prev = temp;                       
                                                 }                       
           
                                                 // now traverse from both the corners                       
                                                 next_node = NULL;                       
                                                 prev = NULL;                       
           
                                                 // here if we want to move forward then we must                       
                                                 // know the prev address to calculate next node                       
                                                 // and if we want to move backward then we must                       
                                                 // know the next_node address to calculate prev node                       
                                                 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                                     ;                       
           
                                                 // move first in forward                       
                                                 struct                                     Node *temp = first;                       
                                                 first = XOR(first->next,prev);                       
                                                 prev = temp;                       
           
                                                 // move second in backward                       
                                                 temp = second;                       
                                                 second = XOR(second->next, next_node);                       
                                                 next_node = temp;                       
                                                 }                       
                                                 else                       
                                                 {                       
                                                 if                                     ((first->data + second->data) < x)                       
                                                 {                       
                                                 // move first in forward                       
                                                 struct                                     Node *temp = first;                       
                                                 first = XOR(first->next,prev);                       
                                                 prev = temp;                       
                                                 }                       
                                                 else                       
                                                 {                       
                                                 // move second in backward                       
                                                 struct                                     Node *temp = second;                       
                                                 second = XOR(second->next, next_node);                       
                                                 next_node = temp;                       
                                                 }                       
                                                 }                       
                                                 }                       
                                                 if                                     (flag ==                                     false                                     )                       
                                                 cout <<                                     "No pair found"                                     << endl;                       
                         }                       
           
                         // Driver program to run the case                       
                         int                                     main()                       
                         {                       
                                                 /* Start with the empty list */                       
                                                 struct                                     Node* head = NULL;                       
                                                 int                                     x = 17;                       
           
                                                 /* Use insert() to construct below list                       
                                                 3-->6-->7-->8-->9-->10-->11 */                       
                                                 insert(&head, 11);                       
                                                 insert(&head, 10);                       
                                                 insert(&head, 9);                       
                                                 insert(&head, 8);                       
                                                 insert(&head, 7);                       
                                                 insert(&head, 6);                       
                                                 insert(&head, 3);                       
           
                                                 // convert singly linked list into XOR doubly                       
                                                 // linked list                       
                                                 convert(head);                       
                                                 pairSum(head,x);                       
                                                 return                                     0;                       
                         }                       

输出：

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

时间复杂度：O（n）

如果链表没有排序，那么我们可以首先对链表进行排序。但在这种情况下，总体时间复杂度将变成O（n logn）。如果额外的空间不是约束条件，我们可以在这种情况下使用哈希。基于散列的解决方案与方法2相同在这里 . 本文由 沙申克·米什拉（古卢） .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄到contribute@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章