AlgoViz
HomeLinked List

Find Pairs with Given Sum in Doubly Linked List

Medium

Two pointers from both ends

Problem

Given the head of a sorted doubly linked list of positive distinct integers, and a target integer, return a 2D array containing all unique pairs of nodes (a, b) such that a + b == target. Each pair should be returned as a 2-element array [a, b] with a < b. The list is sorted in ascending order. If there are no such pairs, return an empty list.

In simple words

Since it's sorted, use two pointers from both ends: move inward based on whether the sum is too big or small.

The idea

The list is sorted and doubly linked, so you can walk inwards from the head and the tail exactly as with a sorted array: too small means advance the left pointer, too large means retreat the right one.

The trick

  • Finding the tail costs one O(n) pass up front.
  • Stop when the pointers meet or cross.
  • The prev pointers are what make walking backwards possible at all.

This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.

1
2
4
5
6
8
9
0
1
2
3
4
5
6

Step 1 of 2. Here's the example — head = [1, 2, 4, 5, 6, 8, 9], target = 7 Values: 1, 2, 4, 5, 6, 8, 9.

1/2
Optimal
timeO(n)spaceO(1)
1left = head; right = tail2while left != right and right.next != left:3  s = left.val + right.val4  if s == target: record(left,right); left=left.next; right=right.prev5  elif s < target: left = left.next6  else: right = right.prev

Input

array
[1, 2, 4, 5, 6, 8, 9]

Output

answer
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:
list = 1 -> 2 -> 4 -> 5 -> 6 -> 8 -> 9, sum = 7
Output:
[[1, 6], [2, 5]]
Explanation:
Pairs (1,6) and (2,5) add to 7.

Example 2

Input:
list = 1 -> 2 -> 3, sum = 4
Output:
[[1, 3]]
Explanation:
Only (1,3).

Example 3

Input:
list = 1 -> 2, sum = 9
Output:
[]
Explanation:
No pair → none.

Constraints

  • 0 <= number of nodes <= 10^5
  • 1 <= Node.val <= 10^5
  • 1 <= target <= 10^5
  • The linked list is sorted in strictly increasing order
  • The linked list is contains distinct values

Practice this problem:GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.