You are given a sorted doubly linked list of size N, consisting of positive integers, and also provided a number K. Your task is to find out whether there exists a pair in the doubly linked list with sum K or not. If there exists a pair then you can return TRUE else return FALSE.
A doubly linked list is a type of linked list that is bidirectional, that is, it can be traversed in both directions, forward and backward.
The first line of input contains a single integer T, representing the number of test cases.
Then the T test cases follow.
The first line of every test case contains the elements of the doubly linked list separated by a single space and terminated by -1. Hence, -1 would never be a list element.
For each test case Return “YES” if there exists a pair with a sum equal to K else Return “NO”.
The output of every test case will be printed in a separate line.
You don’t have to print anything, it has already been taken care of. Just implement the given function.
1<= T <=100
2 <= N <= 10^4
0 <= data <= 10^3
1 <= K <= 10^4
Time limit: 1 second
Sample input 1:
1 2 3 4 9 -1
1 10 11 12 27 -1
1 3 4 10 -1
Sample output 1
Explanation for sample output 1
(i) For the first doubly linked list [1,2,3,4,9] there exists a pair (1,3) with a sum equal to 4.
(ii) For the second doubly linked list, there is no pair with a sum equal to 10.
(iii) For the third doubly linked list there exists a pair (3,4) with a sum equal to 7.
Sample input 2:
1 4 5 6 9 12 -1
1 1 10 -1
1 2 10 12 21 -1
Sample output 2:
Explanation for sample output 2
(i) For the first doubly linked list, there is no pair with a sum equal to 20.
(ii) For the second doubly linked list there exists a pair (1,1) with a sum equal to 2.
(iii) For the third doubly linked list, there is no pair with a sum equal to 5.