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.
The idea is to reverse the second half of the linked list and utilize the twin's definition by simultaneously traversing the first half from the beginning and the reversed half from the end. As you do this traversal, calculate the twin sums and keep track of the maximum.
Steps:
This solution involves reversing the second half of the linked list, which is achieved with the reverseList function. After that, we compare nodes from the start of the first and the new reversed lists to find and return the maximum twin sum.
Time Complexity: O(n), where n is the number of nodes in the linked list.
Space Complexity: O(1), as we only use a constant amount of additional space.
This approach makes use of an auxiliary array where we store the values of the linked list nodes. Once stored, we can leverage the structure of the list to easily compute twin sums using simple array indexing.
Steps:
An auxiliary array is used to read the linked list node values. Then, a loop calculates the twin sums through array indices and computes the maximum sum.
Time Complexity: O(n).
Space Complexity: O(n), due to the auxiliary array.
We can store the values of the nodes in the linked list into an array, then use two pointers pointing to the beginning and end of the array to calculate the twin sum for each pair of twin nodes. The maximum twin sum is the answer.
The time complexity is O(n) and the space complexity is O(n), where n is the number of nodes in the linked list.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Two-pointer with Reverse | Time Complexity: O(n), where n is the number of nodes in the linked list. |
| Auxiliary Array Storage | Time Complexity: O(n). |
| Simulation | — |
| Default Approach | — |
| 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 |
Maximum Twin Sum of a Linked List - Leetcode 2130 - Python • NeetCodeIO • 24,056 views views
Watch 9 more video solutions →Practice Maximum Twin Sum of a Linked List with our built-in code editor and test cases.
Practice on FleetCode