22. Count Triplets in a sorted doubly linked list whose sum is equal to a given value x

22. Count Triplets in a sorted doubly linked list whose sum is equal to a given value x

Problem link :- click here

package Linked_List;

public class LinkedList__22
{

	static int countTriplets(DoublyLinkedList list, int sum)
	{
		if(list.head == null  ||  list.head.next == null  ||  list.head.next.next ==null)
			return 0;
		
		int count = 0;
		
		Node2 first, second, third;
		first = list.head;
		for(first=list.head; first.next.next != null; first=first.next)
		{
			second = first.next;
			third = first.next;
			while(third.next != null)
				third = third.next;
			
			while(second != third   &&   second.prev != third)
			{
				int sum1 = first.data + second.data + third.data;
				if(sum == sum1)
				{
					count++;
					System.out.println("(" + first.data + ", " + second.data + 
										", " + third.data + ")");
					second = second.next;
					third = third.prev;
				}
				else
				{
					if(sum < sum1)
						third = third.prev;
					
					else
						second = second.next;
				}
			}
		}
		
		return count;
	}
	
	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);
		
		System.out.println("Doubly linked list : ");
		list.print();
		
		int sum = 17;
		int ans = countTriplets(list, sum);
		if(ans == 0)
			System.out.println("No such triplet");
	}

}

Time complexity :- O(n^2)
Space complexity :- O(1)