Maximum Twin Sum of a Linked List
Medium · Linked Lists · Linked List · Two Pointers · Stack
Problem
A singly linked list has an even number of nodes, n. Counting from 0, node i and node n - 1 - i are twins for every i < n / 2: the first and the last node, the second and the second to last, and so on.
The twin sum of a pair is the sum of their values. Given the head of the list, return the largest twin sum.
A singly linked list can only be walked forwards, so the twin of an early node is not at hand when you reach it.
Examples
Input: head = [5,4,2,1] Output: 6
The twins are (5, 1) and (4, 2): both sum to 6.
Input: head = [4,2,2,3,1,9] Output: 13
The sums are 4 + 9 = 13, 2 + 1 = 3 and 2 + 3 = 5.
Input: head = [1,100000] Output: 100001
Two nodes are one pair of twins.
Constraints
- 2 <= number of nodes <= 10^5
- the number of nodes is even
- 1 <= Node.val <= 10^5
Approaches
- Copy the values to an array — time O(n), space O(n)
Follow-up
Pushing the first half onto a stack also pairs the twins, at O(n) space. The use cases keep the pairing and change the question: whether every twin sum is equal, and the largest gap between twins.
Related problems
Start free on Cariara · Coding problems · System design studio
