Skip to main content
Talentd

Maximum Twin Sum of a Linked List - Solution & Explanation

MediumLinked ListTwo PointersStack24 min readAsked at: Amazon, Microsoft, Meta +3
Practice this problem

Problem Statement

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.

  • 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.

 

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:

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

Approach Overview

Problem 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 1: Two-pointer with Reverse

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:

  1. Find the midpoint of the linked list using a slow and fast pointer approach.
  2. Reverse the second half of the linked list.
  3. Initialize pointers to traverse the first half and the reversed second half simultaneously.
  4. Calculate twin sums and update the maximum twin sum.

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 2: Auxiliary Array Storage

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:

  1. Traverse the linked list to populate an array with node values.
  2. Using a loop, calculate twin sums by adding corresponding elements from the start and end of the array.
  3. Track the maximum sum obtained.

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n).
Space Complexity: O(n), due to the auxiliary array.

Try this approach in the editor →

Approach 3: Simulation

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.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Approach 4: Default Approach

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Two-pointer with Reverse

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.

Auxiliary Array Storage

Time Complexity: O(n).
Space Complexity: O(n), due to the auxiliary array.

Simulation—
Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Auxiliary Array StorageO(n)O(n)Best when you want a simple implementation or when modifying the linked list is not allowed
Two-Pointer with ReverseO(n)O(1)Optimal interview solution when memory efficiency matters

Video Solution

Maximum Twin Sum of a Linked List - Leetcode 2130 - Python • NeetCodeIO • 25,656 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Maximum Twin Sum of a Linked List easy or hard?
Maximum Twin Sum of a Linked List is classified as a Medium problem on LeetCode. The difficulty comes from combining multiple linked list techniques: finding the middle, reversing a list segment, and processing pairs efficiently.
Maximum Twin Sum of a Linked List Python/Java solution
Python and Java implementations typically follow the same pattern: find the midpoint using slow and fast pointers, reverse the second half of the list, then compute twin sums by traversing both halves together. This approach runs in O(n) time and O(1) extra space.
How to solve Maximum Twin Sum of a Linked List in O(n)?
Find the midpoint of the linked list using slow and fast pointers. Reverse the second half of the list in-place. Then iterate through the first half and the reversed second half simultaneously, computing the twin sum for each pair and tracking the maximum value.
What is the best approach for Maximum Twin Sum of a Linked List?
The best approach uses the two-pointer technique with in-place reversal of the second half of the linked list. First find the middle using slow and fast pointers, reverse the second half, then compute twin sums while traversing both halves together. This achieves O(n) time and O(1) extra space.
Is Maximum Twin Sum of a Linked List asked at Google/Amazon/Meta?
Linked list pointer manipulation problems like this commonly appear in interviews at companies such as Amazon, Google, and Meta. Variants involving reversing half a list, finding midpoints, or pairwise comparisons are standard interview patterns.
What data structure is used in Maximum Twin Sum of a Linked List?
The core data structure is a singly linked list. Solutions may also use an auxiliary array for easier indexing or rely on two-pointer techniques and in-place list reversal to keep the space complexity constant.
What is the time complexity of Maximum Twin Sum of a Linked List?
The optimal solution runs in O(n) time because the list is traversed a constant number of times: once to find the middle, once to reverse the second half, and once to compute twin sums. Each operation is linear with respect to the number of nodes.

Ready to solve this problem?

Practice Maximum Twin Sum of a Linked List with our built-in code editor and test cases.

Practice on FleetCode
Previous

Middle of the Linked List

Next

Palindrome Linked List