Find pairs with given sum in doubly linked list | C ++ program to find a pair with given sum x . ; structure of node of doubly linked list ; Function to find pair whose sum equal to given value x . ; Set two pointers , first to the beginning of DLL and second to the end of DLL . ; To track if we find a pair or not ; The loop terminates when two pointers cross each other ( second -> next == first ) , or they become same ( first == second ) ; pair found ; move first in forward direction ; move second in backward direction ; if pair is not present ; A utility function to insert a new node at the beginning of doubly linked list ; Driver program
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct Node { int data ; struct Node * next , * prev ; } ; void pairSum ( struct Node * head , int x ) { struct Node * first = head ; struct Node * second = head ; while ( second -> next != NULL ) second = second -> next ; bool found = false ; while ( first != second && second -> next != first ) { if ( ( first -> data + second -> data ) == x ) { found = true ; cout << " ( " << first -> data << " , ▁ " << second -> data << " ) " << endl ; first = first -> next ; second = second -> prev ; } else { if ( ( first -> data + second -> data ) < x ) first = first -> next ; else second = second -> prev ; } } if ( found == false ) cout << " No ▁ pair ▁ found " ; } 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 ; } } 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 ; }