⚡Flashcard Drill➔
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

  1. Find the middle with slow/fast pointers, then reverse the second half.
  2. Now the twin pairs are aligned: the first node of the first half and the first node of the reversed second half are twins.
  3. Walk both halves together and take the maximum sum.
  4. 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, so b drives the loop.
  • Forgetting that n is 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.
🎯 Drill This Card Now➔

🧩 Related Linked List Problems