Problem statement

A singly linked list has an even number of nodes n. Counting from 0, node i and node n - 1 - i are called twins for every 0 <= i <= n / 2 - 1: the first node pairs with the last, the second with the second-to-last, and so on. A twin sum is the sum of the values of two twins.

Given the head of such a list, return the largest twin sum.

Example 1

Input: head = [3,8,1,6]
Output: 9
Explanation: The twin pairs are (3, 6) and (8, 1), with sums 9 and 9.

Example 2

Input: head = [4,2,2,3]
Output: 7
Explanation: The twin sums are 4 + 3 = 7 and 2 + 2 = 4; the larger is 7.

Example 3

Input: head = [1,100000]
Output: 100001
Explanation: Two nodes are each other's twin.

Constraints

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

Hints for Maximum Twin Sum of a Linked List

1. Hint 1

   Node i pairs with node n - 1 - i, so the first half is read forwards while the second half is read backwards.

2. Hint 2

   Find the start of the second half with a slow/fast pointer race.

3. Hint 3

   Reverse the second half in place; then walk the first half and the reversed second half side by side, adding pairs.

How to solve Maximum Twin Sum of a Linked List

Twins mirror each other around the middle, so if the second half is reversed the twins line up: walking both halves together visits each twin pair once.

Approach

1. Move slow one step and fast two steps from the head until fast runs out; slow is then the first node of the second half (index n / 2).
2. Reverse the list starting at slow; call its new head second.
3. Walk first = head and second together until second ends, tracking the largest first.val + second.val.

Why it works

After reversal the k-th node of the reversed half is original index n - 1 - k, while the k-th node from the head is index k — exactly a twin pair, for every k < n / 2.

Complexity

• Time — O(n)
• Space — O(1)

Pitfalls

• With an even length, slow lands on index n / 2 when fast becomes null — the start of the second half, not the end of the first.
• Copying the values into an array also works in O(n) time but uses O(n) memory; the in-place reversal is what interviewers look for.

Reference solution

Python

from typing import Optional

def pairSum(head: Optional[ListNode]) -> int:
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    prev = None  # reverse the second half
    while slow:
        slow.next, prev, slow = prev, slow, slow.next
    best = 0
    while prev:
        best = max(best, head.val + prev.val)
        head = head.next
        prev = prev.next
    return best

Java

public static 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; // reverse the second half
    while (slow != null) { ListNode nx = slow.next; slow.next = prev; prev = slow; slow = nx; }
    int best = 0;
    for (ListNode a = head, b = prev; b != null; a = a.next, b = b.next) best = Math.max(best, a.val + b.val);
    return best;
}

C++

int pairSum(ListNode* head) {
    ListNode *slow = head, *fast = head;
    while (fast && fast->next) { slow = slow->next; fast = fast->next->next; }
    ListNode* prev = nullptr; // reverse the second half
    while (slow) { ListNode* nx = slow->next; slow->next = prev; prev = slow; slow = nx; }
    int best = 0;
    for (ListNode *a = head, *b = prev; b; a = a->next, b = b->next) best = max(best, a->val + b->val);
    return best;
}

JavaScript

var pairSum = function(head) {
    var slow = head, fast = head;
    while (fast !== null && fast.next !== null) { slow = slow.next; fast = fast.next.next; }
    var prev = null; // reverse the second half
    while (slow !== null) { var nx = slow.next; slow.next = prev; prev = slow; slow = nx; }
    var best = 0;
    for (var a = head, b = prev; b !== null; a = a.next, b = b.next) best = Math.max(best, a.val + b.val);
    return best;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More two pointers problems

• Merge Two Sorted Linked Lists in Reverse Order Medium
• Rotate a Linked List Medium
• Segregate Even and Odd Nodes in a Linked List Medium
• Delete the Middle Node of a Linked List Medium
• Swapping Nodes in a Linked List Medium
• Merge In Between Linked Lists Medium