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

Popular posts from this blog

4.Sort an array of 0's, 1's & 2's.

1. Reverse

3. Height of Binary tree