TL;DR
Find the middle, reverse the second half, sweep both halves in lockstep — O(n) time, O(1) space.
Approach 1 — Brute force: walk to each twin
For each node at position i, walk from the head n - 1 - i steps to reach its twin, and take the max of the sums.
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
def pairSum(head: Optional[ListNode]) -> int:
n = 0
node = head
while node:
n += 1
node = node.next
best = 0
node = head
for i in range(n // 2):
twin = head
for _ in range(n - 1 - i):
twin = twin.next
best = max(best, node.val + twin.val)
node = node.next
return best
Time O(n^2), space O(1). With n up to 10^5, ~10^10 pointer hops is far past any time limit.
Approach 2 — Copy values into an array
Insight: twins are defined by positions, and positions are trivial with random access. Dump the values into a Python list and pair index i with index n - 1 - i directly.
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
def pairSum(head: Optional[ListNode]) -> int:
vals: List[int] = []
node = head
while node:
vals.append(node.val)
node = node.next
n = len(vals)
return max(vals[i] + vals[n - 1 - i] for i in range(n // 2))
Walkthrough on [4, 2, 2, 3]: vals = [4, 2, 2, 3], n = 4. i=0 pairs 4+3=7; i=1 pairs 2+2=4. Max is 7.
Time O(n), space O(n) for the copied values.
Approach 3 — Middle + reverse second half (optimal)
Insight: the twin pairs are the first half aligned position by position with the reversed second half. Locate the middle with the slow/fast pointer technique (fast moves two steps per slow’s one, so when fast reaches the end, slow is at the midpoint), reverse the second half in place, then walk the two halves together.
After the reversal, [5, 4, 2, 1] splits into a first half and a reversed second half that line up as twins:
flowchart LR
subgraph First["First half"]
A[5] --> B[4]
end
subgraph Second["Second half reversed"]
C[1] --> D[2]
end
A -. twin .- C
B -. twin .- D
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
def pairSum(head: Optional[ListNode]) -> int:
# 1. slow/fast to find the start of the second half
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
# 2. reverse the second half in place
prev = None
while slow:
nxt = slow.next
slow.next = prev
prev = slow
slow = nxt
# 3. lockstep sweep: prev heads 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
Walkthrough on [5, 4, 2, 1]:
- slow/fast: slow ends at the node
2 (index 2), the start of the second half.
- Reversing
2 → 1 yields 1 → 2; prev points at 1.
- Lockstep: (5,1) → 6, then (4,2) → 6. Answer: 6. (Note
first still runs into the old, now-severed half — but the loop is bounded by second, which is exactly n/2 nodes.)
Time O(n) (three linear passes), space O(1).
Common pitfalls
- Bounding the final loop by
first instead of second — after the reversal the first half’s last node still points into the second half in some variants, so always iterate exactly n/2 steps via second.
- Off-by-one in the slow/fast loop: with
while fast and fast.next, slow lands on node n/2 for even n, which is exactly the start of the second half here.
- Forgetting the list is guaranteed even-length and adding dead odd-length handling that obscures the logic.
- Initializing
best = head.val or similar instead of 0 — harmless here since values are positive, but the clean invariant is “max over pairs seen so far”, starting empty.
Pattern takeaway
“Fold the list in half” problems (palindrome check, twin sums, reorder) all reduce to the same three steps: slow/fast to find the middle, in-place reversal of one half, and a lockstep walk of the two halves. Once you know the pattern, each of these becomes a straightforward application of it.