Problem Statement in English

You’re given the head of a singly linked list. Your task is to find the maximum twin sum.

The twin of any node is the node that is at the same position in the second half of the linked list.

So in this list,

    graph LR
    A((1)) --- B((7))
    B --- C((77))
    C --- D((11))

The twin of 1 is 11, and the twin of 7 is 77, and so the max twin sum is $7 + 77 = 84$.

Approach

This problem builds on a previous problem where we had to find the middle of a linked list.

Once we have the middle, we can reverse the first half of the linked list and then iterate over the two halves simultaneously in order to find the maximum twin sum.

Solution in Python


from collections import deque


class Solution:
    def pairSum(self, head: Optional[ListNode]) -> int:
        fast, slow = head, head

        while fast and fast.next:
            fast = fast.next.next

            assert slow != None
            slow = slow.next

        # slow is now the mid

        # store a reference to the second half
        assert slow != None
        head2 = slow

        # reverse from head to mid
        # im going to use a stack
        temp = head
        stack = deque()

        while temp != head2:
            stack.append(temp)
            assert temp != None
            temp = temp.next

        head1 = stack.pop()
        temp = head1

        while len(stack) != 0:
            temp.next = stack.pop()
            temp = temp.next

        s = 0
        # iterate over reversed half and remaining half in order
        while head1 and head2:
            s = max(s, head1.val + head2.val)
            head1 = head1.next
            head2 = head2.next

        return s

Complexity

  • Time: $O(n)$
    Since we iterate over $n$ elements at most.

  • Space: $O(n)$
    Since we use a stack to reverse the half the linked list.

And we are done.