2130. Maximum Twin Sum of a Linked List

[fockspaces]

1. 快慢指針找中點
2. 把後半部翻轉
3. 一一遍歷，找 max_sum

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def pairSum(self, head: Optional[ListNode]) -> int:
        def reverse(head, prev = None):
            if not head:
                return prev
            next_node = head.next
            head.next = prev
            prev = head
            return reverse(next_node, prev)
        slow = fast = head
        max_sum = 0
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

        reverse_head = reverse(slow)
        while head and reverse_head:
            max_sum = max(max_sum, head.val + reverse_head.val)
            head, reverse_head = head.next, reverse_head.next
        return max_sum