Maximum Twin Sum of a Linked List
Problem
The list has even length. Pair node 0 with node n−1, node 1 with n−2, and so on. Return the largest such pair sum. Find the middle with slow/fast, reverse the back half, then walk the two halves together summing pairs.
head = 4 → 2 → 7 → 1 → 9 → 3 → null11def max_twin_sum(head):
a = []
n = head
while n:
a.append(n.val); n = n.next
best = 0
for i in range(len(a) // 2):
s = a[i] + a[-1 - i]
if s > best: best = s
return bestfunction maxTwinSum(head) {
const a = [];
for (let n = head; n; n = n.next) a.push(n.val);
let best = 0;
for (let i = 0; i < a.length / 2; i++) {
const s = a[i] + a[a.length - 1 - i];
if (s > best) best = s;
}
return best;
}class Solution {
public int maxTwinSum(ListNode head) {
List<Integer> a = new ArrayList<>();
for (ListNode n = head; n != null; n = n.next) a.add(n.val);
int best = 0;
for (int i = 0; i < a.size() / 2; i++) {
int s = a.get(i) + a.get(a.size() - 1 - i);
if (s > best) best = s;
}
return best;
}
}int maxTwinSum(ListNode* head) {
vector<int> a;
for (ListNode* n = head; n; n = n->next) a.push_back(n->val);
int best = 0;
for (int i = 0; i < (int)a.size() / 2; i++) {
int s = a[i] + a[(int)a.size() - 1 - i];
if (s > best) best = s;
}
return best;
}Explanation
The list has even length, and a "twin" of node i is the node mirrored from the other end. We pair the first with the last, the second with second-to-last, and so on, then report the largest of these pair sums.
The simplest way to reach both ends of each pair easily is to first copy all the values into an array a. Once they sit in an array, the twin of index i is just index a.length - 1 - i (written a[-1 - i] in Python) — instant access from either side.
Then we loop i from 0 up to n/2, compute s = a[i] + a[-1 - i] for each twin pair, and keep the running maximum in best. After half a pass we have checked every pair exactly once.
Example: 4 → 2 → 7 → 1 → 9 → 3. The pairs are 4 + 3 = 7, 2 + 9 = 11, and 7 + 1 = 8. The largest is 11.
This version uses an array, so it costs O(n) extra space. The same result can be achieved in O(1) space by finding the middle with slow/fast pointers and reversing the back half, but the array approach is the clearest to read.