Watch 10 video solutions for Maximum Twin Sum of a Linked List, a medium level problem involving Linked List, Two Pointers, Stack. This walkthrough by NeetCodeIO has 24,056 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
In a linked list of size n, where n is even, the ith 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.
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.
Example 1:
Input: head = [5,4,2,1] Output: 6 Explanation: Nodes 0 and 1 are the twins of nodes 3 and 2, respectively. All have twin sum = 6. There are no other nodes with twins in the linked list. Thus, the maximum twin sum of the linked list is 6.
Example 2:
Input: head = [4,2,2,3] Output: 7 Explanation: The nodes with twins present in this linked list are: - Node 0 is the twin of node 3 having a twin sum of 4 + 3 = 7. - Node 1 is the twin of node 2 having a twin sum of 2 + 2 = 4. Thus, the maximum twin sum of the linked list is max(7, 4) = 7.
Example 3:
Input: head = [1,100000] Output: 100001 Explanation: There is only one node with a twin in the linked list having twin sum of 1 + 100000 = 100001.
Constraints:
[2, 105].1 <= Node.val <= 105Problem Overview: You receive an even-length singly linked list. The first node pairs with the last node, the second with the second-last, and so on. Each pair forms a twin sum. The task is to compute the maximum twin sum among all pairs.
Approach 1: Auxiliary Array Storage (O(n) time, O(n) space)
Traverse the linked list once and store every node value in an array. Once you have random access, computing twin sums becomes trivial: use two indices i and n-1-i to represent twin pairs. Iterate from the start of the array to the midpoint, compute arr[i] + arr[n-1-i], and track the maximum. The key insight is converting the sequential structure of a linked list into an indexable array so you can access symmetric elements efficiently. This approach is straightforward to implement and easy to reason about, which makes it a good baseline solution.
Approach 2: Two-Pointer with Reverse (O(n) time, O(1) space)
This is the optimal approach and relies on the classic two pointers technique. Use a slow and fast pointer to find the middle of the list. Once the middle is located, reverse the second half of the list in-place. Now the first half and the reversed second half line up so that corresponding nodes represent twin pairs. Walk both halves simultaneously, compute each twin sum, and keep the maximum. The key advantage is that reversing the second half eliminates the need for extra storage while still giving direct access to mirrored nodes.
During the traversal, each step processes exactly one pair: firstHalf.val + secondHalf.val. Since the list is only scanned a few times and the reversal happens in linear time, the overall complexity remains O(n) time with O(1) additional space.
Recommended for interviews: The two-pointer with in-place reverse approach is what interviewers typically expect. It demonstrates strong understanding of linked list manipulation, pointer control, and memory optimization. The auxiliary array solution still shows correct reasoning and is often acceptable as a first step, but the constant-space solution highlights deeper problem-solving skill.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Auxiliary Array Storage | O(n) | O(n) | Best when you want a simple implementation or when modifying the linked list is not allowed |
| Two-Pointer with Reverse | O(n) | O(1) | Optimal interview solution when memory efficiency matters |