Problem Description

You are given a linked list with an even number of nodes. In this linked list, certain nodes form "twin" pairs based on their positions.

For a linked list of size n (where n is even), the twin relationship is defined as:

• Node at position i is the twin of node at position (n-1-i)
• This relationship exists for all nodes where 0 <= i <= (n/2) - 1

For example, in a linked list with 4 nodes:

• Node 0 (first node) is the twin of node 3 (last node)
• Node 1 (second node) is the twin of node 2 (third node)

The twin sum is calculated by adding the values of a node and its twin together.

Your task is to find the maximum twin sum among all possible twin pairs in the linked list.

Example walkthrough: If the linked list is 1 -> 2 -> 3 -> 4:

• Twin pair (node 0, node 3): sum = 1 + 4 = 5
• Twin pair (node 1, node 2): sum = 2 + 3 = 5
• Maximum twin sum = 5

The solution approach converts the linked list to an array for easier access to elements. It then iterates through the first half of the array, calculating the sum of each element with its twin (accessed using negative indexing s[-(i + 1)] which corresponds to the twin position). The maximum of all these twin sums is returned as the answer.

Intuition

The key insight is recognizing that finding twins in a linked list requires accessing nodes from both ends simultaneously - we need to pair the first node with the last, the second with the second-to-last, and so on.

In a linked list, we can only traverse forward, making it difficult to access nodes from the end efficiently. To find the twin of node i, we'd need to traverse to position (n-1-i), which would be inefficient if done repeatedly.

This naturally leads us to think about converting the linked list to a data structure that allows random access - an array. Once we have all values in an array s, finding twins becomes straightforward:

• For any index i in the first half, its twin is at index n-1-i
• Using Python's negative indexing, s[-(i+1)] gives us the twin element directly

The transformation simplifies our problem from "traverse a linked list in a complex pattern" to "iterate through half an array and access corresponding elements from the end". We only need to check the first n/2 elements since each twin pair is counted exactly once.

The expression range(n >> 1) efficiently gives us indices for the first half (using bit shift for division by 2), and for each index i, we calculate s[i] + s[-(i + 1)] to get the twin sum. The maximum of all these sums is our answer.

This approach trades a small amount of extra space O(n) for much simpler and cleaner logic compared to more complex solutions that might try to manipulate the linked list directly.

Learn more about Stack, Linked List and Two Pointers patterns.

Solution Approach

The implementation follows a straightforward two-phase approach:

Phase 1: Convert Linked List to Array

s = []
while head:
    s.append(head.val)
    head = head.next

We traverse the entire linked list once, extracting each node's value and storing it in an array s. This gives us O(1) access to any element by index, which is crucial for efficiently finding twin pairs.

Phase 2: Find Maximum Twin Sum

n = len(s)
return max(s[i] + s[-(i + 1)] for i in range(n >> 1))

After getting the array length n, we use a generator expression to calculate all twin sums:

• range(n >> 1) iterates through indices 0 to (n/2 - 1), covering exactly the first half of the array
• The bit shift operation n >> 1 is equivalent to n // 2, efficiently dividing by 2
• For each index i, we calculate the twin sum using s[i] + s[-(i + 1)]

The negative indexing pattern s[-(i + 1)] deserves special attention:

• When i = 0: s[-1] gives the last element (twin of first)
• When i = 1: s[-2] gives the second-to-last element (twin of second)
• This pattern continues for all elements in the first half

The max() function efficiently finds the largest twin sum among all pairs in a single pass.

Time Complexity: O(n) - we traverse the linked list once and then iterate through half the array Space Complexity: O(n) - we store all node values in the array s

Example Walkthrough

Let's walk through the solution with a linked list: 5 -> 4 -> 2 -> 1

Step 1: Convert Linked List to Array

Starting with the linked list, we traverse it and build an array:

• Visit node with value 5, add to array: s = [5]
• Visit node with value 4, add to array: s = [5, 4]
• Visit node with value 2, add to array: s = [5, 4, 2]
• Visit node with value 1, add to array: s = [5, 4, 2, 1]

Step 2: Calculate Twin Sums

Now we have n = 4 elements. We iterate through the first half (n >> 1 = 2 iterations):

Iteration 1 (i = 0):

• First element: s[0] = 5
• Its twin using negative indexing: s[-(0 + 1)] = s[-1] = 1
• Twin sum: 5 + 1 = 6

Iteration 2 (i = 1):

• Second element: s[1] = 4
• Its twin using negative indexing: s[-(1 + 1)] = s[-2] = 2
• Twin sum: 4 + 2 = 6

Step 3: Find Maximum

Among all twin sums calculated: [6, 6] The maximum twin sum is 6

This demonstrates how the negative indexing pattern s[-(i + 1)] naturally pairs each element in the first half with its corresponding twin from the end, allowing us to find the maximum twin sum efficiently.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n) where n is the number of nodes in the linked list.

• The first while loop traverses the entire linked list once to store all values in the array s, which takes O(n) time.
• The max() function with generator expression iterates through half of the array (n >> 1 which is n/2 iterations), performing constant time addition and comparison operations in each iteration, which takes O(n/2) = O(n) time.
• Overall time complexity: O(n) + O(n) = O(n)

Space Complexity: O(n) where n is the number of nodes in the linked list.

• The array s stores all n values from the linked list, requiring O(n) additional space.
• The generator expression in max() uses O(1) space as it generates values one at a time.
• Overall space complexity: O(n)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Attempting In-Place Solution Without Proper List Reversal

A common mistake is trying to optimize space by avoiding the array conversion and instead attempting to find twins directly in the linked list. Developers might try to use two pointers without properly handling the list structure:

Incorrect Approach:

def pairSum(self, head: Optional[ListNode]) -> int:
    slow = fast = head
    # Try to find middle
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
  
    # Problem: Can't access twins without reversing!
    max_sum = 0
    current = head
    while current != slow:
        # We can't access the twin node from the second half
        # without additional data structure or reversal
        current = current.next
    return max_sum

Solution: If you want to avoid using extra array space, you need to:

1. Find the middle of the linked list
2. Reverse the second half
3. Compare pairs from both halves
4. (Optional) Restore the original list structure

def pairSum(self, head: Optional[ListNode]) -> int:
    # Find middle using slow/fast pointers
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
  
    # Reverse second half
    prev = None
    current = slow
    while current:
        next_temp = current.next
        current.next = prev
        prev = current
        current = next_temp
  
    # Calculate max twin sum
    max_sum = 0
    first_half = head
    second_half = prev
  
    while second_half:
        max_sum = max(max_sum, first_half.val + second_half.val)
        first_half = first_half.next
        second_half = second_half.next
  
    return max_sum

2. Off-by-One Errors in Index Calculation

When manually calculating twin indices, developers often make mistakes with the formula:

Incorrect:

# Wrong twin calculation
max_sum = max(values[i] + values[n - i] for i in range(n // 2))  # Off by one!

Correct:

# Correct twin calculation
max_sum = max(values[i] + values[n - 1 - i] for i in range(n // 2))

The twin of index i is at position n - 1 - i, not n - i. Remember that array indices go from 0 to n-1.

3. Not Handling Edge Cases Properly

While the problem guarantees an even number of nodes, defensive programming suggests validating assumptions:

def pairSum(self, head: Optional[ListNode]) -> int:
    if not head or not head.next:
        return 0  # Handle edge case gracefully
  
    values = []
    current = head
    while current:
        values.append(current.val)
        current = current.next
  
    n = len(values)
    # Verify even length (as per problem constraints)
    assert n % 2 == 0, "List must have even number of nodes"
  
    return max(values[i] + values[n - 1 - i] for i in range(n // 2))