Maximum Twin Pair Sum

medium linked list two pointers

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.

Inputhead = 4 → 2 → 7 → 1 → 9 → 3 → null

Output11

Pairs: 4+3=7, 2+9=11, 7+1=8 → max 11.

node values (even count, comma-separated)

def 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 best

function 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;
}

Time: O(n) Space: O(n) (or O(1) with reverse-half trick)