LeetCode Solutions Blog

Maximum Twin Sum of a Linked List

Number: 2236

Difficulty: Medium

Paid? No

Problem Description

Given the head of an even length linked list, each node at index i (0-indexed) forms a twin with the node at index n-1-i. The twin sum of a pair is the sum of the node values. The task is to return the maximum twin sum among all twin pairs in the linked list.

Key Insights

The linked list has an even number of nodes.
The first half of the list pairs with the reversed second half of the list.
By reversing the second half, the twin pairs can be iterated in one pass simultaneously.
Use the two-pointer technique (slow and fast) to find the midpoint of the list.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1) (if reversing the second half in-place)

Solution

We can solve the problem by first locating the middle of the list using the slow and fast pointer technique. Once we have the middle, we reverse the second half of the list in-place. Then, we iterate through both halves simultaneously, computing the twin sum for each pair and tracking the maximum sum encountered. This approach avoids extra space for an array and completes the solution in a single pass (after the reverse process).

Code Solutions

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def pairSum(self, head: ListNode) -> int:
        # Use two pointers to find the middle of the linked list.
        slow = head
        fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        
        # Reverse the second half of the linked list.
        prev = None
        curr = slow
        while curr:
            next_node = curr.next
            curr.next = prev
            prev = curr
            curr = next_node
        
        # Now, 'prev' is the head of the reversed second half.
        max_sum = 0
        first_half = head
        second_half = prev
        while second_half:
            # Compute the twin sum for the current nodes.
            current_sum = first_half.val + second_half.val
            max_sum = max(max_sum, current_sum)
            # Move both pointers.
            first_half = first_half.next
            second_half = second_half.next
        return max_sum