Find Pairs with a Given Sum in a Doubly Linked List

Medium20–25 min

Topics

Linked ListDoubly Linked ListTwo Pointers

Companies

AmazonMicrosoftFlipkart

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.

Test Case 1:

Input:head = [1, 2, 4, 5, 6, 8, 9], target = 10

Output:[[1, 9], [2, 8], [4, 6]]

Explanation:Three pairs sum to 10; 5 is left over with no partner.

Test Case 2:

Input:head = [1, 2, 3], target = 10

Output:[]

Explanation:No pair reaches the target sum, so the answer is empty.

Test Case 3:

Input:head = [-3, -1, 0, 2, 5], target = 2

Output:[[-3, 5], [0, 2]]

Explanation:Negative values work the same way — -3 + 5 = 2 and 0 + 2 = 2.

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

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

Approach & Solutions

Brute Force — Check Every Pair

Good

For every node, walk every node after it and check whether the two values add up to the target. It's simple and doesn't need the list to be sorted, but it re-examines every later node for every earlier one — quadratic work even though the list is already sorted and a much faster scan is possible.

TimeO(n²)

SpaceO(1) extra

Java

Try it out

// Node definition used in this problem:
// class Node {
//     int val;
//     Node next;
// }

class Solution {
    public int[][] findPairsSum(Node head, int target) {
        List<int[]> pairs = new ArrayList<>();
        for (Node a = head; a != null; a = a.next) {
            for (Node b = a.next; b != null; b = b.next) {
                if (a.val + b.val == target) {
                    pairs.add(new int[]{a.val, b.val});
                    break;
                }
            }
        }
        return pairs.toArray(new int[0][]);
    }
}

Optimal — Two Pointers from Both Ends

Optimal

Since the list is sorted, a left pointer starting at head and a right pointer starting at the tail can close in on each other, exactly like the two-pointer technique on a sorted array. If the sum at left + right is too small, left moves forward (to grow the sum); if it's too big, right moves backward (to shrink it); if it's exactly the target, that pair is recorded and both pointers move in — one pass covers the whole list. Walking backward from the tail needs a real .prev pointer, so an internal doubly linked copy (with .prev) is built first from the input chain — and since there's no index to compare positions with, a running count of how many nodes are still left to check (instead of comparing pointers) is what tells the loop when to stop.

TimeO(n)