learnleetcode

2130. Maximum Twin Sum of a Linked List

Medium · solved 2026-10-05 · Open on LeetCode

linked-listtwo-pointers

Time O(n) · Space O(1)

How to get there

Fold the list in half

1. Restate the pairs. Node i’s twin is node n − 1 − i: the first node with the last, the second with the second-to-last. Folding the list in half lines every node up with its twin.

2. Pair [5, 4, 2, 1] by hand and find where one pass gets stuck. The twins are (5, 1) and (4, 2). Walking forward, the 5’s twin is the last node, reached only at the end, and by then the 5 is far behind with no way back.

3. Find what to remember. One half has to be read backwards while the other is read forwards. Last in, first out is a stack: push the second half’s values, then pop them while walking from the head, so the last node meets the first, as in solution-2-stack.py. A full copy read from both ends works too, as in solution-1-original.py. Either way it costs O(n) space.

4. Remove the storage by reordering the second half. The list itself can be made to read in the order the pairs need. Find the middle with fast and slow pointers (as in 2095), reverse the second half in place (as in 206), then walk the first half and the reversed second half side by side: each step meets one pair of twins.

5. Check the cost. Three passes over at most n nodes: O(n) time, and a few pointers: O(1) space. The input list is left rewired.

The reusable recipe: when a sequence is matched against its own reverse, either store one half on a stack, or reverse one half in place and walk both halves forward together.

One meaning per loop

Each of the three loops keeps its own pair of pointers true:

Loop Variables Always mean, at the top of the loop, after i turns
find the middle slow, fast the nodes at index i and 2i
reverse the second half prev, slow the head of the reversed part, and the head of the part not yet reversed
sum the twins front, back twins: the nodes at index i and n − 1 − i
sum the twins best the largest twin sum among the first i pairs

Where each loop stops:

Loop Stops when Which leaves
while fast: fast is None, at index n slow at index n/2, the first node of the second half
while slow: the second half is used up prev on the last node, the head of the reversed second half
while back: back has walked the n/2 reversed nodes best over every pair

while fast: needs no fast.next check: fast only lands on even indices, and n is even, so fast is never the last node. The second loop is 206’s loop, with slow in the role of node. In the third, back stops after exactly n/2 steps, so front never walks past the first half.

The method carries over: give each loop its own meaning, and solve its stop condition for what the next loop needs.

Alternatives compared

Approach Time Space How it works
Copy into a deque, pop both ends (solution-1-original.py) O(n) O(n) Copy every value, then pop one from each end per pair.
Copy into a list, index the twins O(n) O(n) Copy every value, then take values[i] + values[n - 1 - i] for each i in the first half.
Stack of the second half (solution-2-stack.py) O(n) O(n) Find the middle, push the second half’s values, then pop one per node while walking from the head.
Reverse the second half (chosen, solution-3-reverse-half.py) O(n) O(1) Find the middle, reverse the second half in place, then walk both halves together.

The stack and the reversal do the same job: both make the second half read from its end. The stack holds that order in n/2 values, and the reversal holds it in the list’s own next pointers. So the copies leave the input list untouched, and the chosen approach rewires it. On a 100,000-node list in CPython, measured on one machine, solution-1-original.py took about 10 ms, solution-2-stack.py about 9 ms, and the chosen approach about 8 ms: the gain is memory more than speed.

solution-1-original.py

# 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: ListNode | None) -> int:
        ls, cursor, best = deque([]), head, 0

        while cursor:
            ls.append(cursor.val)
            cursor = cursor.next

        while ls:
            left, right = ls.popleft(), ls.pop()
            best = max(best, left+right)

        return best

solution-2-stack.py

# 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: ListNode | None) -> int:
        slow, fast = head, head
        stack = []
        best = 0

        while fast:
            slow, fast = slow.next, fast.next.next

        while slow:
            stack.append(slow.val)
            slow = slow.next

        while stack:
            best = max(best, head.val+stack.pop())
            head = head.next

        return best

solution-3-reverse-half.py

# 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: ListNode | None) -> int:
        slow, fast = head, head
        while fast:
            slow = slow.next
            fast = fast.next.next

        prev = None
        while slow:
            next_node = slow.next
            slow.next = prev
            prev = slow
            slow = next_node

        best = 0
        front, back = head, prev
        while back:
            best = max(best, front.val + back.val)
            front = front.next
            back = back.next
        return best

Notes

Write your approach, insights, and mistakes here. Any other file in this folder (e.g. solution.py, attempt-1.py) is rendered below as code.