Find Pair with given sum in Doubly Linked List

Today we will be discussing how to Find Pair of elements from doubly linked list with given sum. But if you are new to doubly linked list then please refer to this link where I have explained everything about doubly linked list. Suppose you have a doubly linked list like 1-2-3-4-5 and you have to find pair of elements which adds up to 5 then you should get the output as (1,4) and (2,3). Now let's discuss the procedure:

Procedure

1. First we will make a linked list.

2. Then we will iterate the list by using 2 loops.

3. Suppose the outer loop is run by a variable 'x' and inner loop is run by a variable 'y'.

4. Thus 'x' will start iterating from 1st node till 2nd last node of the list.

5. And 'y' will iterate from next node of 'x' till the last node of the list.

6. In this way each pair of node will be compared and we can easily find the pair of nodes with given sum.

Code

#include<iostream> using namespace std; struct node { int data; struct node* next; }; struct node* head=NULL; class linked { public: void insert(int x) { struct node* temp=new node(); temp->data=x; temp->next=NULL; if(head==NULL) { head=temp; } else { struct node* temp1=head; while(temp1->next!=NULL) { temp1=temp1->next; } temp1->next =temp; } } void sum(int s) { struct node* temp=head; while(temp->next!=NULL) { struct node* temp1=temp->next; while(temp1!=NULL) { if(temp->data + temp1->data ==s) { cout<<"("<<temp->data<<","<<temp1->data<<")"<<endl; } temp1=temp1->next; } temp=temp->next; } } void disp() { struct node* temp=head; while(temp!=NULL) { cout<<temp->data<<" "; temp=temp->next; } cout<<endl; } }; int main() { linked l; l.insert(5); l.insert(3); l.insert(-4); l.insert(7); l.insert(-6); l.insert(0); l.insert(9); l.insert(18); l.disp(); int s; cout<<"Enter sum that you want to find in the doubly linked list: "; cin>>s; l.sum(s); return 0; }

Explanation of Code 

1. First we will write a simple code of doubly linked list which will have 2 functions:

     - insert() - which will insert elements in the doubly linked list.
     - disp() - which will display the doubly linked list.

2. Insert some values in the doubly linked list.
3. Now we have created a function named sum() for find pair of nodes which adds up to given sum. It takes an argument 's' which contain desired sum we have to find. 

4. Then we have created a pointer to node variable 'temp' which is initialized to head.

    struct node* temp=head;

5. Then we have used a while loop to iterate temp from 1st node till 2nd last node of the list.

     while(temp->next!=NULL)
     {

              ----------

     }

6. Now we have created another pointer to node which is temp1 and initialized it with next node of temp.

    struct node* temp1=temp->next;

7. Next we have iterated temp1 till the end of the list.

    while(temp1!=NULL)
    { 

         -----------

    }

8. Inside temp1 's while loop we have placed a if condition to check if the sum of data at temp and data at temp1 is equal to the sum 's' passed in the function. 

   if(temp->data + temp1->data ==s)
   { 

        ----------

  }

 9. If the sum of temp's data and temp1 's data is equal to s the we have printed the pair of nodes inside if condition.

   cout<<"("<<temp->data<<","<<temp1->data<<")"<<endl;

10. Then we have incremented temp1.

   temp1=temp1->next;

11. Outside this loop we have incremented temp.

    temp=temp->next;