LeetCode - The World's Leading Online Programming Learning Platform

Approach

1. Split list into two parts
2. Revers the second part
3. Loop through two parts at once, find max sum

Complexity

• Time complexity:O(n)
• Space complexity:O(1)

Code

# 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:
        # divide list into two parts
        fast, slow = head.next, head
        while fast.next:
            fast = fast.next.next
            slow = slow.next
        part_head = slow.next
        slow.next = None
        # reverse list part_head -> result: part_prev
        part_prev = None
        part_cur = part_head
        while part_cur:
            part_next = part_cur.next
            part_cur.next = part_prev
            part_prev, part_cur = part_cur, part_next
        # go through two parts, find max sum
        max_sum = 0
        while part_prev and head:
            max_sum = max(max_sum, part_prev.val+head.val)
            part_prev = part_prev.next
            head = head.next
        return max_sum