Maximum Twin Sum of a Linked List solution and explanation
Google
9 more videos on this problem
Maximum Twin Sum of a Linked List - Leetcode 2130 - PythonNeetCodeIO · 8:59 · 25K views
Maximum Twin Sum of a Linked List | 3 Approaches | GOOGLE | Leetcode-2130 | Live Code + ExplanationcodestorywithMIK · 25:57 · 10K views
Maximum Twin Sum of a Linked List || Slow & Fast Pointer || Reverse a Linked List || C++/Java/PythonAryan Mittal · 13:37 · 4K views
Maximum Twin Sum of a Linked List - LeetCode 2130 - Python #leetcode75Deepti Talesra · 10:16 · 2K views
2130. Maximum Twin Sum of a Linked List (Leetcode Medium)Programming Live with Larry · 6:49 · 1K views
Maximum Twin Sum of a Linked List - Leetcode 2130 - PythonTechError · 6:35 · 737 views
Maximum Twin Sum of a Linked List - LeetCode 2130 - Python SolutionCode with Carter · 11:25 · 485 views
Leetcode 2130: Maximum Twin Sum of a Linked List - Java Solution with visualisationpredecode · 14:51 · 407 views
Solving the '2130. Maximum Twin Sum of a Linked List' Problem in Java LeetCode 75 Study PlanCoding with Christian · 9:44 · 325 views
Leetcode 2130. Maximum Twin Sum of a Linked List - 2 methods: 1. without reverse; 2. with reverseCode-Yao · 14:48 · 220 views
The problem
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 node0is the twin of node3, and node1is the twin of node2. These are the only nodes with twins forn = 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:
- Find the midpoint of the linked list using a slow and fast pointer approach.
- Reverse the second half of the linked list.
- Initialize pointers to traverse the first half and the reversed second half simultaneously.
- Calculate twin sums and update the maximum twin sum.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def reverseList(self, head):
prev = None
current = head
while current:
nxt = current.next
current.next = prev
prev = current
current = nxt
return prev
def pairSum(self, head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
second_half = self.reverseList(slow)
max_twin_sum = 0
first_half = head
while second_half:
twin_sum = first_half.val + second_half.val
max_twin_sum = max(max_twin_sum, twin_sum)
first_half = first_half.next
second_half = second_half.next
return max_twin_sumclass ListNode {
int val;
ListNode next;
ListNode(int val) {
this.val = val;
}
}
public class Solution {
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode current = head;
while (current != null) {
ListNode nextTemp = current.next;
current.next = prev;
prev = current;
current = nextTemp;
}
return prev;
}
public int pairSum(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
ListNode secondHalf = reverseList(slow);
int maxTwinSum = 0;
ListNode firstHalf = head;
while (secondHalf != null) {
int twinSum = firstHalf.val + secondHalf.val;
maxTwinSum = Math.max(maxTwinSum, twinSum);
firstHalf = firstHalf.next;
secondHalf = secondHalf.next;
}
return maxTwinSum;
}
}#include <iostream>
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* prev = nullptr;
ListNode* current = head;
while (current) {
ListNode* nextTemp = current->next;
current->next = prev;
prev = current;
current = nextTemp;
}
return prev;
}
int pairSum(ListNode* head) {
ListNode* slow = head;
ListNode* fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
ListNode* secondHalf = reverseList(slow);
int maxTwinSum = 0;
ListNode* firstHalf = head;
while (secondHalf) {
int twinSum = firstHalf->val + secondHalf->val;
maxTwinSum = std::max(maxTwinSum, twinSum);
firstHalf = firstHalf->next;
secondHalf = secondHalf->next;
}
return maxTwinSum;
}
};function ListNode(val, next) {
this.val = (val===undefined ? 0 : val)
this.next = (next===undefined ? null : next)
}
var reverseList = function(head) {
let prev = null;
let current = head;
while (current !== null) {
let nextTemp = current.next;
current.next = prev;
prev = current;
current = nextTemp;
}
return prev;
};
var pairSum = function(head) {
let slow = head;
let fast = head;
while (fast !== null && fast.next !== null) {
slow = slow.next;
fast = fast.next.next;
}
let secondHalf = reverseList(slow);
let maxTwinSum = 0;
let firstHalf = head;
while (secondHalf !== null) {
let twinSum = firstHalf.val + secondHalf.val;
maxTwinSum = Math.max(maxTwinSum, twinSum);
firstHalf = firstHalf.next;
secondHalf = secondHalf.next;
}
return maxTwinSum;
};struct ListNode {
int val;
struct ListNode *next;
};
struct ListNode* reverseList(struct ListNode* head) {
struct ListNode* prev = NULL;
struct ListNode* curr = head;
while (curr) {
struct ListNode* nextTemp = curr->next;
curr->next = prev;
prev = curr;
curr = nextTemp;
}
return prev;
}
int pairSum(struct ListNode* head) {
struct ListNode* slow = head;
struct ListNode* fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
struct ListNode* secondHalf = reverseList(slow);
int maxTwinSum = 0;
struct ListNode* firstHalf = head;
while (secondHalf) {
int twinSum = firstHalf->val + secondHalf->val;
if(twinSum > maxTwinSum) maxTwinSum = twinSum;
firstHalf = firstHalf->next;
secondHalf = secondHalf->next;
}
return maxTwinSum;
}public class ListNode {
public int val;
public ListNode next;
public ListNode(int val=0, ListNode next=null) {
this.val = val;
this.next = next;
}
}
public class Solution {
public ListNode ReverseList(ListNode head) {
ListNode prev = null;
ListNode current = head;
while (current != null) {
ListNode nextTemp = current.next;
current.next = prev;
prev = current;
current = nextTemp;
}
return prev;
}
public int PairSum(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
ListNode secondHalf = ReverseList(slow);
int maxTwinSum = 0;
ListNode firstHalf = head;
while (secondHalf != null) {
int twinSum = firstHalf.val + secondHalf.val;
maxTwinSum = Math.Max(maxTwinSum, twinSum);
firstHalf = firstHalf.next;
secondHalf = secondHalf.next;
}
return maxTwinSum;
}
}This solution in Python finds the middle of the linked list, reverses the second half, computes the twin sums, and returns the greatest twin sum found.
Time Complexity: O(n).
Space Complexity: O(1).
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:
- Traverse the linked list to populate an array with node values.
- Using a loop, calculate twin sums by adding corresponding elements from the start and end of the array.
- Track the maximum sum obtained.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def pairSum(self, head):
values = []
current = head
while current:
values.append(current.val)
current = current.next
max_twin_sum = 0
n = len(values)
for i in range(n // 2):
twin_sum = values[i] + values[n - 1 - i]
max_twin_sum = max(max_twin_sum, twin_sum)
return max_twin_sumimport java.util.ArrayList;
class ListNode {
int val;
ListNode next;
ListNode(int val) {
this.val = val;
}
}
public class Solution {
public int pairSum(ListNode head) {
ArrayList<Integer> values = new ArrayList<>();
ListNode current = head;
while (current != null) {
values.add(current.val);
current = current.next;
}
int maxTwinSum = 0;
int n = values.size();
for (int i = 0; i < n / 2; i++) {
int twinSum = values.get(i) + values.get(n - 1 - i);
maxTwinSum = Math.max(maxTwinSum, twinSum);
}
return maxTwinSum;
}
}#include <vector>
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(nullptr) {}
};
class Solution {
public:
int pairSum(ListNode* head) {
std::vector<int> values;
ListNode* temp = head;
while (temp) {
values.push_back(temp->val);
temp = temp->next;
}
int maxTwinSum = 0;
int n = values.size();
for (int i = 0; i < n / 2; ++i) {
int twinSum = values[i] + values[n - 1 - i];
maxTwinSum = std::max(maxTwinSum, twinSum);
}
return maxTwinSum;
}
};function ListNode(val, next) {
this.val = (val===undefined ? 0 : val)
this.next = (next===undefined ? null : next)
}
var pairSum = function(head) {
let values = [];
let current = head;
while (current !== null) {
values.push(current.val);
current = current.next;
}
let maxTwinSum = 0;
const n = values.length;
for (let i = 0; i < n / 2; i++) {
const twinSum = values[i] + values[n - 1 - i];
maxTwinSum = Math.max(maxTwinSum, twinSum);
}
return maxTwinSum;
};#include <stdlib.h>
#include <string.h>
struct ListNode {
int val;
struct ListNode *next;
};
int max(int a, int b) {
return (a > b) ? a : b;
}
int pairSum(struct ListNode* head) {
int n = 0;
struct ListNode* temp = head;
while (temp) {
n++;
temp = temp->next;
}
int* arr = (int*)malloc(sizeof(int) * n);
temp = head;
for (int i = 0; i < n; i++) {
arr[i] = temp->val;
temp = temp->next;
}
int maxTwinSum = 0;
for (int i = 0; i < n / 2; i++) {
int twinSum = arr[i] + arr[n - 1 - i];
maxTwinSum = max(maxTwinSum, twinSum);
}
free(arr);
return maxTwinSum;
}using System;
using System.Collections.Generic;
public class ListNode {
public int val;
public ListNode next;
public ListNode(int val=0, ListNode next=null) {
this.val = val;
this.next = next;
}
}
public class Solution {
public int PairSum(ListNode head) {
List<int> values = new List<int>();
ListNode current = head;
while (current != null) {
values.Add(current.val);
current = current.next;
}
int maxTwinSum = 0;
int n = values.Count;
for (int i = 0; i < n / 2; i++) {
int twinSum = values[i] + values[n - 1 - i];
maxTwinSum = Math.Max(maxTwinSum, twinSum);
}
return maxTwinSum;
}
}This solution adopts an auxiliary list to gather the values from the nodes, enabling simple index-based operations to find the maximum twin sum.
Time Complexity: O(n).
Space Complexity: O(n).
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.
/**
* Definition for singly-linked list.
* class ListNode {
* val: number
* next: ListNode | null
* constructor(val?: number, next?: ListNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
* }
*/
function pairSum(head: ListNode | null): number {
const arr = [];
let node = head;
while (node) {
arr.push(node.val);
node = node.next;
}
const n = arr.length;
let ans = 0;
for (let i = 0; i < n >> 1; i++) {
ans = Math.max(ans, arr[i] + arr[n - 1 - i]);
}
return ans;
}/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func pairSum(head *ListNode) int {
var s []int
for ; head != nil; head = head.Next {
s = append(s, head.Val)
}
ans, n := 0, len(s)
for i := 0; i < (n >> 1); i++ {
if ans < s[i]+s[n-i-1] {
ans = s[i] + s[n-i-1]
}
}
return ans
}// Definition for singly-linked list.
// #[derive(PartialEq, Eq, Clone, Debug)]
// pub struct ListNode {
// pub val: i32,
// pub next: Option<Box<ListNode>>
// }
//
// impl ListNode {
// #[inline]
// fn new(val: i32) -> Self {
// ListNode {
// next: None,
// val
// }
// }
// }
impl Solution {
pub fn pair_sum(head: Option<Box<ListNode>>) -> i32 {
let mut arr = Vec::new();
let mut node = &head;
while node.is_some() {
let t = node.as_ref().unwrap();
arr.push(t.val);
node = &t.next;
}
let n = arr.len();
let mut ans = 0;
for i in 0..n >> 1 {
ans = ans.max(arr[i] + arr[n - 1 - i]);
}
ans
}
}Approach 4: Default Approach
/**
* Definition for singly-linked list.
* class ListNode {
* val: number
* next: ListNode | null
* constructor(val?: number, next?: ListNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
* }
*/
function pairSum(head: ListNode | null): number {
let fast = head;
let slow = head;
while (fast) {
fast = fast.next.next;
slow = slow.next;
}
let prev = null;
while (slow) {
const next = slow.next;
slow.next = prev;
prev = slow;
slow = next;
}
let left = head;
let right = prev;
let ans = 0;
while (left && right) {
ans = Math.max(ans, left.val + right.val);
left = left.next;
right = right.next;
}
return ans;
}/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func pairSum(head *ListNode) int {
reverse := func(head *ListNode) *ListNode {
dummy := &ListNode{}
curr := head
for curr != nil {
next := curr.Next
curr.Next = dummy.Next
dummy.Next = curr
curr = next
}
return dummy.Next
}
slow, fast := head, head.Next
for fast != nil && fast.Next != nil {
slow, fast = slow.Next, fast.Next.Next
}
pa := head
q := slow.Next
slow.Next = nil
pb := reverse(q)
ans := 0
for pa != nil {
ans = max(ans, pa.Val+pb.Val)
pa = pa.Next
pb = pb.Next
}
return ans
}Complexity comparison
| Approach | Complexity |
|---|---|
| Two-pointer with Reverse | Time Complexity: O(n). |
| Auxiliary Array Storage | Time Complexity: O(n). |
| Simulation | – |
| Default Approach | – |
Complexity analysis
| 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 |
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.