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".

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.

---