[5/17] 2130. Maximum Twin Sum of a Linked List

# Time Complexity: O(n), Space Complexity: O(1)

class Solution:
    def pairSum(self, head: Optional[ListNode]) -> int:
        # Use fast and slow, 2 pointers, the slow will be the half
        slow = fast = head
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next

        # Reverse the half. It will be the backward
        cur, prev = slow, None
        while cur:
            curNext = cur.next
            cur.next = prev
            prev = cur
            cur = curNext

        # Calculate the max sum adding forward and backward
        maxSum = float('-inf')
        forward, backward = head, prev
        while backward:
            maxSum = max(maxSum, + forward.val + backward.val)
            forward, backward = forward.next, backward.next
        return maxSum