[Leetcode] 2130. Maximum Twin Sum of a Linked List (tuple unpacking)

https://leetcode.com/problems/maximum-twin-sum-of-a-linked-list/description/?envType=study-plan-v2&envId=leetcode-75

initial

I had noidea.
But this requires reversing the first half of list via 1 slow and 1 fast pointer that moves twice as fast.

Then, the slow pointer will be at the exact middle of the given linked list. We iterate this slow pointer that traverses the other half of the list and the reversed list together.

VERY IMPT tuple unpacking

        while fast and fast.next:
            fast=fast.next.next
            slow.next, prev, slow = prev, slow, slow.next

The order of tuple unpacking matters. The expressions on the right are all evaluated first before assiging them on those left variables. This is the correct order. You first change the next pointer of the current slow node to point to the previous node. Then you shift the prev pointer forward to the current slow node, and then shift the slow pointer forward to the next node.

If we had

slow, prev, slow.next = slow.next, slow, prev

The problem here is that you're changing slow before you change slow.next. This means that when you try to set slow.next to prev, you're now working with the new slow (which is the old slow.next), rather than the original slow. This will corrupt your linked list.

solution

class Solution:
    def pairSum(self, head: Optional[ListNode]) -> int:
        slow,fast=head,head
        while fast and fast.next:
            slow=slow.next
            fast=fast.next.next
        prev=None
        while slow:
            tmp=slow.next
            slow.next=prev
            prev=slow
            slow=tmp
        ans=0
        while prev:
            ans= max(ans,prev.val+head.val)
            prev=prev.next
            head=head.next
        return ans
        

complexity

o(n) time
o(1) space