Find Pairs with a Given Sum in a Doubly Linked List
Implement findPairsSum
Given the head of a doubly linked list sorted in non-decreasing order and an integer target, find all pairs of nodes whose values add up to target — each node used in at most one pair — and return the pairs.
Because the list is already sorted, this is the linked-list version of the classic "two-sum on a sorted array" two-pointer trick — except walking backward from the tail uses a real .prev pointer instead of an index, which is exactly the kind of operation a doubly linked list makes cheap that a singly linked list can't do at all.
Example 1:
Input: head = [1,2,4,5,6,8,9], target = 10
Output: [[1,9],[2,8],[4,6]]
Example 2:
Input: head = [1,2,3], target = 10
Output: []
Example 3:
Input: head = [-3,-1,0,2,5], target = 2
Output: [[-3,5],[0,2]]
+ 4 hidden test cases run on Submit.
Constraints:
- ●
0 ≤ number of nodes in head ≤ 200 - ●
-1000 ≤ node value, target ≤ 1000 - ●
head is sorted in non-decreasing order - ●
each node may be used in at most one pair
head =
[1, 2, 4, 5, 6, 8, 9]
target =
10