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)