Maximum Twin Sum of a Linked List
MediumUpdated: Oct 12, 2025
Practice on:
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.
Examples
Example 1
graph LR E(5):::blue --> D(4):::red --> B(2):::red --> A(1):::blue classDef red fill:#FF0000,stroke:#000,stroke-width:1px,color:#fff; classDef blue fill:#87CEEB,stroke:#333,stroke-width:2px;
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
graph LR D(4):::blue --> B1(2):::red --> B2(2):::red --> C(3):::blue classDef red fill:#FF0000,stroke:#000,stroke-width:1px,color:#fff; classDef blue fill:#87CEEB,stroke:#333,stroke-width:2px;
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
graph LR A(1) --> B1(100000)
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, 10^5]. 1 <= Node.val <= 10^5
Solution
Method 1 – Two Pointers and Reversal
Intuition
The twin sum pairs the first half of the list with the second half in reverse order. By finding the middle, reversing the second half, and pairing nodes, we can efficiently compute all twin sums and track the maximum.
Approach
- Use slow and fast pointers to find the middle of the list.
- Reverse the second half of the list.
- Traverse both halves in parallel, summing corresponding node values.
- Track and return the maximum twin sum found.
Complexity
- ⏰ Time complexity:
O(n)— Each node is visited a constant number of times. - 🧺 Space complexity:
O(1)— In-place reversal, no extra space except pointers.
Code
C++
class Solution {
public:
int pairSum(ListNode* head) {
ListNode *slow = head, *fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
ListNode *prev = nullptr, *cur = slow;
while (cur) {
ListNode *next = cur->next;
cur->next = prev;
prev = cur;
cur = next;
}
int ans = 0;
ListNode *p1 = head, *p2 = prev;
while (p2) {
ans = max(ans, p1->val + p2->val);
p1 = p1->next;
p2 = p2->next;
}
return ans;
}
};
Go
func pairSum(head *ListNode) int {
slow, fast := head, head
for fast != nil && fast.Next != nil {
slow = slow.Next
fast = fast.Next.Next
}
var prev *ListNode
cur := slow
for cur != nil {
next := cur.Next
cur.Next = prev
prev = cur
cur = next
}
ans := 0
p1, p2 := head, prev
for p2 != nil {
if p1.Val+p2.Val > ans { ans = p1.Val + p2.Val }
p1 = p1.Next
p2 = p2.Next
}
return ans
}
Java
class Solution {
public int pairSum(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
ListNode prev = null, cur = slow;
while (cur != null) {
ListNode next = cur.next;
cur.next = prev;
prev = cur;
cur = next;
}
int ans = 0;
ListNode p1 = head, p2 = prev;
while (p2 != null) {
ans = Math.max(ans, p1.val + p2.val);
p1 = p1.next;
p2 = p2.next;
}
return ans;
}
}
Kotlin
class Solution {
fun pairSum(head: ListNode?): Int {
var slow = head
var fast = head
while (fast != null && fast.next != null) {
slow = slow?.next
fast = fast.next.next
}
var prev: ListNode? = null
var cur = slow
while (cur != null) {
val next = cur.next
cur.next = prev
prev = cur
cur = next
}
var ans = 0
var p1 = head
var p2 = prev
while (p2 != null) {
ans = maxOf(ans, p1!!.`val` + p2.`val`)
p1 = p1.next
p2 = p2.next
}
return ans
}
}
Python
def pair_sum(head: 'ListNode') -> int:
slow, fast = head, head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
prev, cur = None, slow
while cur:
nxt = cur.next
cur.next = prev
prev = cur
cur = nxt
ans = 0
p1, p2 = head, prev
while p2:
ans = max(ans, p1.val + p2.val)
p1 = p1.next
p2 = p2.next
return ans
Rust
impl Solution {
pub fn pair_sum(head: Option<Box<ListNode>>) -> i32 {
let mut slow = &head;
let mut fast = &head;
while fast.is_some() && fast.as_ref().unwrap().next.is_some() {
slow = &slow.as_ref().unwrap().next;
fast = &fast.as_ref().unwrap().next.as_ref().unwrap().next;
}
let mut prev = None;
let mut cur = slow.clone();
while let Some(mut node) = cur {
let next = node.next.take();
node.next = prev;
prev = Some(node);
cur = next;
}
let mut ans = 0;
let mut p1 = head;
let mut p2 = prev;
while let (Some(n1), Some(n2)) = (p1, p2) {
ans = ans.max(n1.val + n2.val);
p1 = n1.next;
p2 = n2.next;
}
ans
}
}
TypeScript
class Solution {
pairSum(head: ListNode | null): number {
let slow = head, fast = head
while (fast && fast.next) {
slow = slow.next
fast = fast.next.next
}
let prev: ListNode | null = null, cur = slow
while (cur) {
const next = cur.next
cur.next = prev
prev = cur
cur = next
}
let ans = 0, p1 = head, p2 = prev
while (p2) {
ans = Math.max(ans, p1!.val + p2.val)
p1 = p1!.next
p2 = p2.next
}
return ans
}
}