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:
- Iterate through the list.
- 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.
- If such nodes are found, print the pair.
- 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
- Implement the
searchKey
function to search for a given key in the left or right side of a node. - Implement the
findPairWithSum
function. - If
head
is null or the list has less than two nodes, return. - Initialize
node
ashead.next
. - Iterate through the list using a loop while
node
is not null. - 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.
- If such nodes are found, print the pair and return.
- If no pairs are found, print "None".
Program List
-
1) Find pairs with specific sum in doubly linked list in java
2) Find pairs with specific sum in doubly linked list in c++
3) Find pairs with specific sum in doubly linked list in c
4) Find pairs with specific sum in doubly linked list in c#
5) Find pairs with specific sum in doubly linked list in php
6) Find pairs with specific sum in doubly linked list in python
7) Find pairs with specific sum in doubly linked list in ruby
8) Find pairs with specific sum in doubly linked list in scala
9) Find pairs with specific sum in doubly linked list in node js
10) Find pairs with specific sum in doubly linked list in swift
11) Find pairs with specific sum in doubly linked list in kotlin
12) Find pairs with specific sum in doubly linked list in vb.net
13) Find pairs with specific sum in doubly linked list in golang
14) Find pairs with specific sum in doubly linked list in typescript
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.
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.
New Comment