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

Program List

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.

New Comment