We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Maximum Twin Sum of a Linked List

Difficulty: Medium

Problem Description

Given a linked list of even length, the ith node (0-indexed) is known as the twin of the (n-1-i)th node. The twin sum is defined as the sum of a node and its twin. The task is to return the maximum twin sum of the linked list.

Key Insights

  • The linked list has an even number of nodes, allowing for direct pairing of nodes with their twins.
  • The maximum twin sum can be calculated by summing pairs of nodes that are considered twins.
  • A two-pointer approach can be effectively utilized to find the twin sums without extra space.

Space and Time Complexity

Time Complexity: O(n) - We traverse the linked list twice (once to find the middle and once to compute sums). Space Complexity: O(n) - This is for storing the values in a list if we use that approach. However, a more optimal solution can achieve O(1) space.

Solution

To solve the problem, we can use the following approach:

  1. Traverse the linked list to find its length and store the values in an array.
  2. Calculate the twin sums using the stored values by pairing the first half of the array with the second half.
  3. Keep track of the maximum twin sum encountered during this process.

Code Solutions

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def pairSum(head: ListNode) -> int:
    # Step 1: Store values in an array
    values = []
    current = head
    while current:
        values.append(current.val)
        current = current.next

    # Step 2: Calculate maximum twin sum
    max_sum = 0
    n = len(values)
    for i in range(n // 2):
        twin_sum = values[i] + values[n - 1 - i]
        max_sum = max(max_sum, twin_sum)

    return max_sum
← Back to All Questions