How do you solve Maximum Twin Sum of a Linked List?

Use two pointers (slow and fast) to find the midpoint. Reverse the second half of the list starting from slow. Initialize two pointers at the start of the first half and the reversed second half. Iterate through both halves, compute sums of paired nodes, and track the maximum sum. Return the maximum twin sum found.

Maximum Twin Sum of a Linked List

Q: What is the time complexity of Maximum Twin Sum of a Linked List?

O(n). The algorithm traverses the list a constant number of times: once to find the midpoint, once to reverse the second half, and once to compute twin sums, each linear in the number of nodes.

Q: What pattern does Maximum Twin Sum of a Linked List use?

The Pattern: Linked Lists (Two-Pointer Midpoint and In-Place Reversal) The Heuristic: To efficiently pair nodes from opposite ends of a singly linked list, find the midpoint with slow/fast pointers, reverse the second half in-place, then traverse both halves simultaneously to compute paired values without extra space.

Medium Linked Lists

Problem

Given the head of a singly linked list of even length, return the maximum twin sum of the linked list, where the twin sum is defined as the sum of the values of the ith node from the beginning and the ith node from the end.

The number of nodes in the list is even.
2 ≤ number of nodes ≤ 10⁵
1 ≤ Node.val ≤ 10⁵

Example

Input: head = [5,4,2,1]

Output: 6

The linked list has 4 nodes. The twin pairs are (5,1) and (4,2). Their sums are 6 and 6 respectively. The maximum twin sum is 6. The algorithm first finds the midpoint using slow and fast pointers. Then it reverses the second half of the list to align the twin nodes for direct comparison. Finally, it iterates through both halves simultaneously, calculating sums and tracking the maximum.

Approach

Straightforward Solution

A brute-force approach would involve converting the linked list to an array and then computing twin sums by indexing from both ends. This requires O(n) extra space and two passes, which is suboptimal for large lists.

Core Observation

The twin sum pairs correspond to nodes equidistant from the start and end of the list. To access these pairs efficiently, the list can be split into two halves, with the second half reversed to align pairs for direct traversal.

Path to Optimal

Preview

The key insight is to use the slow and fast pointer technique to find the midpoint in a single pass. Then reverse the second half of the list in-place, enabling simultaneous traversal of both halves to compute twin sums in O(n) time and O(1) space…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Use two pointers (slow and fast) to find the midpoint. Reverse the second half of the list starting from slow…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n)

The algorithm traverses the list a constant number of times: once to find the midpoint, once to reverse the second half, and once to compute twin sums, each linear in the number of nodes.

Space

O(1)

All operations are done in-place with only a fixed number of pointers used, requiring constant auxiliary space regardless of input size.

Pattern Spotlight

Linked Lists (Two-Pointer Midpoint and In-Place Reversal)

To efficiently pair nodes from opposite ends of a singly linked list, find the midpoint with slow/fast pointers, reverse the second half in-place, then traverse both halves simultaneously to compute paired values without extra space.

Solution

Python

1class Solution:
  def pairSum(self, head: Optional[ListNode]) -> int:
      slow = head
      fast = head
5
      while fast and fast.next:
          slow = slow.next
          fast = fast.next.next
9
      prev = None
11
      while slow:
          next_node = slow.next
          slow.next = prev
          prev = slow
          slow = next_node
17
      left = head
      right = prev
      max_sum = 0
21
      while right:
          max_sum = max(max_sum, left.val + right.val)
          left = left.next
          right = right.next
26
      return max_sum

Step-by-Step Solution

Locate Midpoint Using Slow and Fast Pointers

3slow = head
4fast = head
6while fast and fast.next:
7    slow = slow.next
8    fast = fast.next.next

Objective

To find the middle node of the linked list efficiently in a single pass.

Key Insight

Using two pointers moving at different speeds (slow moves one step, fast moves two steps) guarantees that when fast reaches the end, slow is at the midpoint. This technique exploits the linked list's sequential structure to find the midpoint without extra space or length calculation.

Interview Quick-Check

Core Logic

Slow and fast pointers traverse the list at different speeds; when fast reaches the end, slow points to the midpoint.

State & Boundaries

The loop condition `while fast and fast.next` ensures safe traversal without null pointer exceptions.

Common Pitfalls & Bugs

Incorrect loop conditions can cause infinite loops or miss the exact midpoint, especially in even-length lists.

Reverse the Second Half of the List In-Place

To reverse the nodes from the midpoint to the end, enabling direct pairing with the first half.

Traverse Both Halves to Compute and Track Maximum Twin Sum

To iterate through the first half and reversed second half simultaneously, calculating twin sums and tracking the maximum.

Return the Maximum Twin Sum Found

To output the maximum twin sum after completing the traversal.

3 more steps with full analysis available on Pro.

Line Analysis

This solution has 3 Critical lines interviewers watch for.

Line 14 Critical

slow.next = prev

Reverse current node's next pointer to previous node.

This is the critical reversal step that flips the link direction, enabling backward traversal of the second half.

Line 13 Critical

next_node = slow.next

Store next node before reversing current node's pointer.

Saving next_node prevents losing access to the remainder of the list during reversal.

Line 23 Critical

max_sum = max(max_sum, left.val + right.val)

Update max_sum with maximum of current max and sum of paired nodes.

This line computes the twin sum for the current pair and updates max_sum if a larger sum is found, ensuring the final result is correct.

Full line-by-line criticality + rationale for all 19 lines available on Pro.

Test Your Understanding

Why is reversing the second half of the linked list necessary for computing the twin sums efficiently?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Maximum Twin Sum of a Linked List from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Maximum Twin Sum of a Linked List drill

or drill a free problem

1	`class Solution:`
2	`def pairSum(self, head: Optional[ListNode]) -> int:`
3	`slow = head`
4	`fast = head`
5
6	`while fast and fast.next:`
7	`slow = slow.next`
8	`fast = fast.next.next`
9
10	`prev = None`
11
12	`while slow:`
13	`next_node = slow.next`
14	`slow.next = prev`
15	`prev = slow`
16	`slow = next_node`
17
18	`left = head`
19	`right = prev`
20	`max_sum = 0`
21
22	`while right:`
23	`max_sum = max(max_sum, left.val + right.val)`
24	`left = left.next`
25	`right = right.next`
26
27	`return max_sum`

3	`slow = head`
4	`fast = head`
6	`while fast and fast.next:`
7	`slow = slow.next`
8	`fast = fast.next.next`