Posted on by Kalkicode
Code Doubly linked list

# Find pairs with given sum in doubly linked list

In this article, we'll explore how to find pairs with a given sum in a doubly linked list using Java and (c++,python,c# etc). The problem involves searching for two nodes in the linked list whose values add up to the given sum. We'll provide a detailed explanation of the problem, outline the steps to solve it, present a Java code example, and explain the output.

## Problem Statement

Given a doubly linked list and an integer sum, the task is to find pairs of nodes whose values add up to the given sum.

## Example

Consider the following doubly linked list:

``8 <-> 2 <-> 6 <-> 12 <-> -2 <-> 7 <-> 9 <-> 3 <-> 4``

For the sum 5, the pairs with the given sum are (3, 2).

For the sum 23, no pairs with the given sum exist.

## Idea to Solve

To find pairs with a given sum in a doubly linked list, we can follow these steps:

1. Iterate through the list.
2. For each node, check if there is a node in the left or right side of the current node whose value complements the current node's value to reach the given sum.
3. If such nodes are found, print the pair.
4. Continue this process until the end of the list is reached.

## Pseudocode

``````function searchKey(key, first, last):
initialize front as first
initialize rear as last
while front is not null and rear is not null:
if front.data is equal to key or rear.data is equal to key:
return true
if front is equal to rear or front.next is equal to rear:
return false
front = front.next
rear = rear.prev
return false

function findPairWithSum(sum):
if head is null or head.next is null:
return
initialize node as head.next
print "Sum:", sum
while node is not null:
if searchKey(sum - node.data, head, node.prev) or
searchKey(sum - node.data, node.next, tail):
print "Pair (", sum - node.data, ",", node.data, ")"
return
node = node.next
print "None"``````

## Algorithm Explanation

1. Implement the `searchKey` function to search for a given key in the left or right side of a node.
2. Implement the `findPairWithSum` function.
3. If `head` is null or the list has less than two nodes, return.
4. Initialize `node` as `head.next`.
5. Iterate through the list using a loop while `node` is not null.
6. Check if there are nodes on the left or right side of the current node whose values complement the current node's value to reach the given sum.
7. If such nodes are found, print the pair and return.
8. If no pairs are found, print "None".

## Time Complexity

The time complexity of finding pairs with a given sum in a doubly linked list is O(n^2), where n is the number of nodes in the list. In the worst case, we iterate through the list and, for each node, potentially iterate through the remaining nodes to find a complement.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post