Linked List: Find pairs with a given sum in a DLL.

Problem Statement:

You are given a DLL and a value, get the pairs that match the value.

Example

Example: 1 <-> 2 <-> 3 <-> 4 <-> 5 <-> 6 

k = 5

Output:
( 2, 3)

Solution

Method 1: Two pointers Approach

Take 2 pointers “first = head” and “second=last_node”

If the current sum of first and second is less than x, then move the first pointer forward else move the second backwards.

Solution in C++

#include <algorithm>  
//visit www.ProDeveloperTutorial.com for 450+ solved questions  
#include <iostream>    
#include <string>
#include <queue>
#include <vector>
#include <stack> 

using namespace std;
  
struct Node 
{
    int data;
    struct Node* next;
    struct Node *prev;
};
 
void get_pair_sum(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 != NULL && second != NULL && 
        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) == NULL)
        (*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 = 10;
 
    get_pair_sum(head, x);
    return 0;
} 

Output:

(1, 9)
(2, 8)
(4, 6)