Maximum Twin Sum of a Linked List

The key idea

In a list of n nodes (n even), node i is twinned with node n-1-i. The pairs are the first half against the reversed second half. Walk to the middle with a fast/slow pointer, reverse the second half in place, then advance one pointer from the head and one from the new (reversed) tail in lockstep, summing each twin pair and tracking the maximum. This needs only O(1) extra space.

Problem

In a linked list of size n, where n is even, the i-th node (0-indexed) of the linked list is known as the twin of the (n-1-i)-th node, if 0 <= i <= (n / 2) - 1. For example, if n = 4, then node 0 is the twin of node 3, and node 1 is the twin of node 2. These are the only nodes with twins for n = 4. The twin sum is defined as the sum of a node and its twin. Given the head of a linked list with even length, return the maximum twin sum of the linked list.

Constraints

The number of nodes in the list is an even integer in the range [2, 10^5].
1 <= Node.val <= 10^5

Examples

Input: head = [5,4,2,1] Output: 6

Input: head = [4,2,2,3] Output: 7

Input: head = [1,100000] Output: 100001

Complexity

Time: O(n) Space: O(1)

See the full solution

✓Full worked approach
✓Reference code in 5 languages
✓Problem-solving tips
✓Step-by-step animated visualization

410310

Step-by-step visualization

Start free →