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