2130. Maximum Twin Sum of a Linked List.py

"""
2130
In a linked list of size n, where n is even, the ith node (0-indexed) of the linked list is known as the twin of the (n-1-i)th node, if 0 <= i <= (n / 2) - 1.

For example, if n = 4, then node 0 is the twin of node 3, and node 1 is the twin of node 2. These are the only nodes with twins for n = 4.
The twin sum is defined as the sum of a node and its twin.

Given the head of a linked list with even length, return the maximum twin sum of the linked list.
"""

class Solution:
    def pairSum(self, head: Optional[ListNode]) -> int:
        slow_ptr = head
        fast_ptr = head
        prev_ptr = None
        while fast_ptr and fast_ptr.next:
            fast_ptr = fast_ptr.next.next
            next_node = slow_ptr.next
            slow_ptr.next = prev_ptr
            prev_ptr = slow_ptr
            slow_ptr = next_node

        max_sum = float('-inf')
        while slow_ptr:
            max_sum = max(max_sum, slow_ptr.val + prev_ptr.val)
            slow_ptr = slow_ptr.next
            prev_ptr = prev_ptr.next
        return max_sum