21. Find pairs with given sum in doubly linked list
21. Find pairs with given sum in doubly linked list
Problem link :- click here
package Linked_List;
public class LinkedList__21
{
static void findPairSum(DoublyLinkedList list, int sum)
{
if(list.head == null)
return;
Node2 first = list.head;
Node2 second = list.head;
while(second.next != null)
second = second.next;
Boolean found = false;
while(first != second && second.next != first)
{
if(first.data + second.data == sum)
{
found = true;
System.out.println("(" + first.data + ", " + second.data + ")");
first = first.next;
second = second.prev;
}
else
{
if(first.data + second.data < sum)
first = first.next;
else
second = second.prev;
}
}
if(!found)
System.out.println("No such pairs");
}
public static void main(String[] args)
{
DoublyLinkedList list = new DoublyLinkedList();
list.push(1);
list.push(2);
list.push(4);
list.push(5);
list.push(6);
list.push(8);
list.push(9);
int sum = 7;
System.out.println("Doubly linked list : ");
list.print();
System.out.println("\nPairs : ");
findPairSum(list, sum);
}
}
Time complexity :- O(n)
Space complexity :- O(1)
Comments
Post a Comment