< Back





2130. Maximum Twin Sum of a Linked List

We're given a linked list of size n, where n will always be an even number. We're asked to find the
maximum twin sum. Twins are defined as two nodes, one from the beginning and one from the end. For
example, in a linked list with size 4, twins would be (0, 3) and (1, 2).

To solve this, we first find the middle of the linked list using a slow and fast pointer. Then, from
the slow pointer, we begin to reverse the second half of the linked list. After the second half of
the linked list is reverse, we traverse both lists and find the maximum twin sum.

The solution is as follows:


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

          while fast and fast.next:
              fast = fast.next.next
              slow = slow.next
          
          prev = None
          curr = slow
          while curr:
              next_node = curr.next
              curr.next = prev
              prev = curr
              curr = next_node

          ans = 0
          while prev:
              ans = max(ans, prev.val + head.val)
              prev = prev.next
              head = head.next

          return ans


_ Time Complexity:

  O(n) - We traverse all nodes within the linked list.

_ Space Complexity:

  O(1) - We maintain pointers that occupy constant space.