NeetCode #320LC-2130MediumLinked List
← Back to All Problems#320 · #2130 · Maximum Twin Sum of a Linked List(链表最大孪生和)
📌 Problem Statement & Constraints
In a linked list of even length
n, the twin of node i is node n - 1 - i. The twin sum is the sum of a node and its twin. Return the maximum twin sum. Constraints: 2 <= n <= 10^5, n is even, 1 <= Node.val <= 10^5.💡 Core Algorithmic Approaches
- Find the middle with slow/fast pointers, then reverse the second half.
- Now the twin pairs are aligned: the first node of the first half and the first node of the reversed second half are twins.
- Walk both halves together and take the maximum sum.
- This is O(n) time with O(1) extra space, which is the expected optimisation over copying values into an array.
💻 Benchmark Python3 Implementation
class Solution:
def pairSum(self, head: Optional[ListNode]) -> int:
# 1) find the middle (slow lands on the first node of the second half)
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
# 2) reverse the second half
prev = None
cur = slow
while cur:
cur.next, prev, cur = prev, cur, cur.next
# 3) walk both halves in lockstep
a, b = head, prev
best = 0
while b:
best = max(best, a.val + b.val)
a = a.next
b = b.next
return best⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): three linear passes.
💾 Space Complexity
O(1): only pointers.
⚠️ Interview Pitfalls & Follow-ups
- Copying values into an array: correct and simple, but O(n) space.
- Reversing the first half instead: either half works, but the twin alignment requires exactly one reversal.
- Stopping the loop on
a: the reversed half is the shorter one for the middle node, sobdrives the loop. - Forgetting that
nis even: with an even length the halves are equal, so the pairing is exact.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.