Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email
Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!

# Find Pairs With Given Sum In A Doubly Linked List

Last Updated on March 10, 2022 by Ria Pathak

### Problem Statement

In this problem, we will be given a sorted doubly linked list and a target integer. We need to find and print the pairs whose sum is equal to the given target.

Note: The integer value inside each node is unique.

### Problem Statement understanding:

The problem statement is quite straightforward; we need to print pairs whose sum is equal to the given target.

Let’s try to understand the problem with the help of an example:
If the list given to us is:

and the target = 14

• We can easily see that the pairs (2,12) and (4,10) both sum up to the given target of 14.
• So, we need to just print both these pairs as output.

At this point, we have understood the problem statement. Now we will try to formulate an approach for this problem.

##### Brute Force Approach

A straightforward approach to solve this problem is to use nested for loops. Using the outer for loop, pick each node one by one, and then using the inner for loop traverse in the forward direction from the current node to find a second node in the linked list such that the sum of nodes is equal to target.

The time complexity of this approach is O(N2). N is the number of nodes in the linked list.

Although this above approach will work fine, but for longer linked lists having length >= 104, it will give a time limit exceed error. So, now we will try to see some other approaches having less time complexity.

Before jumping onto the optimized approach, try to think about how you can optimize the current approach such that it can find pairs for longer linked lists.

• If stuck, no problem, we will thoroughly see the better approach in the next section.

Let’s move to the approach section.

### Approach

• We will follow two pointer approach in which one pointer will point to the smallest node initially i.e., the first node, and the second one will point to the largest node i.e., the last node.
• Now, we will iterate till both the pointers do not meet each other.
• In every iteration, we will calculate the sum of nodes pointed by both the pointers.
• If the sum is equal to the target, that means we have found the pair, and we have to print it and move the first pointer and the second pointer one node forward and backward, respectively.
• If the sum is smaller than the target, then it means that we need to increase it to make it equal to the target. Since the list is sorted, so moving the first pointer forward will increase the sum.
• If the sum is larger than the target, then it means that we need to decrease it to make it equal to the target. Since the list is sorted, so moving the second pointer backward will decrease the sum.

### Algorithm

1) Initialize two pointers left and right with the first and last node of the list.
2) Run a while loop till both left and right are not equal or adjacent to each other.
3) Calculate the sum of the nodes pointed by the left and the right pointers.

• If the sum equals the target, print both the numbers and move left and right by one node forward and backward, respectively.
• Else if the sum is less than the target, move left forward by one node.
• Else, move right backward by one node.

### Code Implementation

```#include
using namespace std;

class Node
{
public:
int data;
Node* next;
Node* prev;
};

//create node of doubly linked list
Node* new_node = new Node();

//assign the data entered by user
new_node->data = x;

// node is inserted in beginning so, prev will always
// be NULL
new_node->prev = NULL;

//the node created is inserted at beginning so we need to

}

void print_list(Node* node){
while (node != NULL)
{
cout << node->data << ",";
node = node->next;
}
}

//initialize two pointers
//move right pointer to last node
while (right->next != NULL)
right = right->next;

// break the loop when two pointers meet
// each other or cross each other
while (left != right && right->next != left)
{
int sum = (left->data + right->data);
// sum is equal to target so, pair found
if (sum == x)
{
cout << "(" << left->data<< ", "
<< right->data << ")" << endl;

// move left forward by one node
left = left->next;

// move right backward by one node
right = right->prev;
}
else
{
if (sum < x)
left = left->next;
else
right = right->prev;
}
}
}

int main()
{

cout<<"The pairs with sum equal to target are: "<

```

#### Output

The pairs with sum equal to target are:
(2, 12)
(4, 10)

Time Complexity: O(n), n is the total number of nodes in the list.
[forminator_quiz id=”5813″]

So, in this blog, we have tried to explain how we can find a pair with a given sum in a doubly-linked list in the most optimal way. If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes, you can follow this link Linked List.