2130. Maximum Twin Sum of a Linked List

Linked List
Two Pointers
Stack

TIME

O(n)

SPACE

O(1)

Intuition

Twins are the ith and (n-1-i)th nodes, the node pairs you get by walking inward from both ends, exactly like a palindrome check. If we could traverse the second half in reverse while traversing the first half forward, each step would line up a twin pair.

Reversing the second half of the list in place lets us do that with two pointers and only O(1) extra space.

Approach

Use slow/fast pointers to reach the middle: when fast reaches the end, slow is at the start of the second half.
Reverse the second half of the list in place.
Walk one pointer from the original head and another from the head of the reversed second half simultaneously; each step is a twin pair. Track the maximum of first.val + second.val.
Return that maximum.

Complexity

Time: O(n), find middle, reverse half, single pairing pass
Space: O(1), in-place reversal, no extra structures

Edge Cases

Smallest list (n == 2) -> a single twin pair
All equal values -> every twin sum is identical
Maximum values -> twin sum up to 2 * 10^5, well within int

Note

An O(n) time / O(n) space alternative is to push the first half onto a stack, then pop while traversing the second half to form pairs, simpler but uses extra memory.

Code

from typing import Optional


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next


class Solution:
    def pairSum(self, head: Optional["ListNode"]) -> int:
        """
        2130. Maximum Twin Sum of a Linked List
        Time: O(n)
        Space: O(1)
        """
        # Find the middle (start of the second half).
        slow, fast = head, head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

        # Reverse the second half.
        prev = None
        while slow:
            nxt = slow.next
            slow.next = prev
            prev = slow
            slow = nxt

        # Pair the first half with the reversed second half.
        best = 0
        first, second = head, prev
        while second:
            best = max(best, first.val + second.val)
            first = first.next
            second = second.next

        return best

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */

/**
 * 2130. Maximum Twin Sum of a Linked List
 * Time: O(n)
 * Space: O(1)
 */
class Solution {
    public int pairSum(ListNode head) {
        // Find the middle (start of the second half).
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        // Reverse the second half.
        ListNode prev = null;
        while (slow != null) {
            ListNode next = slow.next;
            slow.next = prev;
            prev = slow;
            slow = next;
        }

        // Pair the first half with the reversed second half.
        int best = 0;
        ListNode first = head;
        ListNode second = prev;
        while (second != null) {
            best = Math.max(best, first.val + second.val);
            first = first.next;
            second = second.next;
        }

        return best;
    }
}