给定一个正独立元素的排序双链表，任务是在不使用任何额外空间的情况下，在双链表中查找其和等于给定值x的对？
null
例子：
Input : head : 1 <-> 2 <-> 4 <-> 5 <-> 6 <-> 8 <-> 9 x = 7Output: (6, 1), (5,2)
期望的时间复杂度为O（n），辅助空间为O（1）。
A. 简单方法 对于这个问题，我们需要一个接一个地选取每个节点，并通过正向遍历，在剩余列表中找到第二个元素，其和等于x。这个问题的时间复杂度为O（n^2），n是双链表中的节点总数。
一 有效解决方案 因为这个问题和 这 文章以下是算法：
- 初始化两个指针变量，以在已排序的双链表中查找候选元素。初始化 第一 从双链表开始，即； 第一个=头 初始化 第二 双链表的最后一个节点，即：； 第二个=最后一个节点 .
- 我们初始化 第一 和 第二 指针作为第一个和最后一个节点。这里我们没有随机访问，所以为了找到第二个指针，我们遍历列表来初始化第二个指针。
- 如果当前 第一 和 第二 小于x，我们就移动 第一 在前进方向。如果当前 第一 和 第二 元素大于x，然后我们移动 第二 在向后的方向。
- 循环终止条件也不同于阵列。当两个指针相互交叉（秒->下一个=第一个）或它们变得相同（第一个=第二个）时，循环终止。
- 不存在对的情况将由条件“first==second”处理
C++
// C++ program to find a pair with given sum x. #include<bits/stdc++.h> using namespace std; // structure of node of doubly linked list struct Node { int data; struct Node *next, *prev; }; // Function to find pair whose sum equal to given value x. void pairSum( struct Node *head, int x) { // Set two pointers, first to the beginning of DLL // and second to the end of DLL. struct Node *first = head; struct Node *second = head; while (second->next != NULL) second = second->next; // To track if we find a pair or not bool found = false ; // The loop terminates when two pointers // cross each other (second->next // == first), or they become same (first == second) while (first != second && second->next != first) { // pair found if ((first->data + second->data) == x) { found = true ; cout << "(" << first->data<< ", " << second->data << ")" << endl; // move first in forward direction first = first->next; // move second in backward direction second = second->prev; } else { if ((first->data + second->data) < x) first = first->next; else second = second->prev; } } // if pair is not present if (found == false ) cout << "No pair found" ; } // A utility function to insert a new node at the // beginning of doubly linked list 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; } } // Driver program int main() { struct Node *head = NULL; insert(&head, 9); insert(&head, 8); insert(&head, 6); insert(&head, 5); insert(&head, 4); insert(&head, 2); insert(&head, 1); int x = 7; pairSum(head, x); return 0; } |
JAVA
// Java program to find a // pair with given sum x. class GFG { // structure of node of // doubly linked list static class Node { int data; Node next, prev; }; // Function to find pair whose // sum equal to given value x. static void pairSum( Node head, int x) { // Set two pointers, first // to the beginning of DLL // and second to the end of DLL. Node first = head; Node second = head; while (second.next != null ) second = second.next; // To track if we find a pair or not boolean found = false ; // The loop terminates when // they cross each other (second.next // == first), or they become same // (first == second) while ( first != second && second.next != first) { // pair found if ((first.data + second.data) == x) { found = true ; System.out.println( "(" + first.data + ", " + second.data + ")" ); // move first in forward direction first = first.next; // move second in backward direction second = second.prev; } else { if ((first.data + second.data) < x) first = first.next; else second = second.prev; } } // if pair is not present if (found == false ) System.out.println( "No pair found" ); } // A utility function to insert // a new node at the beginning // of doubly linked list static Node insert(Node head, int data) { Node temp = new Node(); temp.data = data; temp.next = temp.prev = null ; if (head == null ) (head) = temp; else { temp.next = head; (head).prev = temp; (head) = temp; } return temp; } // Driver Code public static void main(String args[]) { Node head = null ; head = insert(head, 9 ); head = insert(head, 8 ); head = insert(head, 6 ); head = insert(head, 5 ); head = insert(head, 4 ); head = insert(head, 2 ); head = insert(head, 1 ); int x = 7 ; pairSum(head, x); } } // This code is contributed // by Arnab Kundu |
Python3
# Python3 program to find a pair with # given sum x. # Structure of node of doubly linked list class Node: def __init__( self , x): self .data = x self . next = None self .prev = None # Function to find pair whose sum # equal to given value x. def pairSum(head, x): # Set two pointers, first to the # beginning of DLL and second to # the end of DLL. first = head second = head while (second. next ! = None ): second = second. next # To track if we find a pair or not found = False # The loop terminates when they # cross each other (second.next == # first), or they become same # (first == second) while (first ! = second and second. next ! = first): # Pair found if ((first.data + second.data) = = x): found = True print ( "(" , first.data, "," , second.data, ")" ) # Move first in forward direction first = first. next # Move second in backward direction second = second.prev else : if ((first.data + second.data) < x): first = first. next else : second = second.prev # If pair is not present if (found = = False ): print ( "No pair found" ) # A utility function to insert a new node # at the beginning of doubly linked list def insert(head, data): temp = Node(data) if not head: head = temp else : temp. next = head head.prev = temp head = temp return head # Driver code if __name__ = = '__main__' : head = None head = insert(head, 9 ) head = insert(head, 8 ) head = insert(head, 6 ) head = insert(head, 5 ) head = insert(head, 4 ) head = insert(head, 2 ) head = insert(head, 1 ) x = 7 pairSum(head, x) # This code is contributed by mohit kumar 29 |
C#
// C# program to find a // pair with given sum x. using System; class GFG { // structure of node of // doubly linked list class Node { public int data; public Node next, prev; }; // Function to find pair whose // sum equal to given value x. static void pairSum( Node head, int x) { // Set two pointers, first // to the beginning of DLL // and second to the end of DLL. Node first = head; Node second = head; while (second.next != null ) second = second.next; // To track if we find a pair or not bool found = false ; // The loop terminates when // they cross each other (second.next // == first), or they become same // (first == second) while (first != second && second.next != first) { // pair found if ((first.data + second.data) == x) { found = true ; Console.WriteLine( "(" + first.data + ", " + second.data + ")" ); // move first in forward direction first = first.next; // move second in backward direction second = second.prev; } else { if ((first.data + second.data) < x) first = first.next; else second = second.prev; } } // if pair is not present if (found == false ) Console.WriteLine( "No pair found" ); } // A utility function to insert // a new node at the beginning // of doubly linked list static Node insert(Node head, int data) { Node temp = new Node(); temp.data = data; temp.next = temp.prev = null ; if (head == null ) (head) = temp; else { temp.next = head; (head).prev = temp; (head) = temp; } return temp; } // Driver Code public static void Main(String []args) { Node head = null ; head = insert(head, 9); head = insert(head, 8); head = insert(head, 6); head = insert(head, 5); head = insert(head, 4); head = insert(head, 2); head = insert(head, 1); int x = 7; pairSum(head, x); } } // This code is contributed by 29AjayKumar |
Javascript
<script> // Javascript program to find a // pair with given sum x. // structure of node of // doubly linked list class Node { constructor() { this .data = 0; this .next = this .prev = null ; } } // Function to find pair whose // sum equal to given value x. function pairSum(head, x) { // Set two pointers, first // to the beginning of DLL // and second to the end of DLL. let first = head; let second = head; while (second.next != null ) second = second.next; // To track if we find a pair or not let found = false ; // The loop terminates when // they cross each other (second.next // == first), or they become same // (first == second) while ( first != second && second.next != first) { // pair found if ((first.data + second.data) == x) { found = true ; document.write( "(" + first.data + ", " + second.data + ")<br>" ); // move first in forward direction first = first.next; // move second in backward direction second = second.prev; } else { if ((first.data + second.data) < x) first = first.next; else second = second.prev; } } // if pair is not present if (found == false ) document.write( "No pair found<br>" ); } // A utility function to insert // a new node at the beginning // of doubly linked list function insert(head,data) { let temp = new Node(); temp.data = data; temp.next = temp.prev = null ; if (head == null ) (head) = temp; else { temp.next = head; (head).prev = temp; (head) = temp; } return temp; } // Driver Code let head = null ; head = insert(head, 9); head = insert(head, 8); head = insert(head, 6); head = insert(head, 5); head = insert(head, 4); head = insert(head, 2); head = insert(head, 1); let x = 7; pairSum(head, x); // This code is contributed by avanitrachhadiya2155 </script> |
输出：
(1,6) (2,5)
时间复杂性： O（n） 辅助空间： O（1）
如果链表没有排序，那么我们可以首先对链表进行排序。但在这种情况下，总体时间复杂度将变成O（n logn）。如果额外的空间不是约束条件，我们可以在这种情况下使用哈希。基于散列的解决方案与方法2相同 在这里 .
本文由 沙申克·米什拉（古卢） .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用 贡献极客。组织 或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
