2130. Maximum Twin Sum Of A Linked List - Explanation

1. Convert To Array

Intuition

A twin sum pairs the i-th node from the start with the i-th node from the end. Since linked lists do not support random access, we first convert the list into an array. With an array, we can use two pointers starting at opposite ends to easily compute each twin sum and track the maximum.

Algorithm

Traverse the linked list and store each node's value in an array arr.
Initialize two pointers: i at the start and j at the end of the array.
While i < j:
- Compute arr[i] + arr[j] and update res if this sum is larger.
- Move i forward and j backward.
Return res.

# 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:
        arr = []
        cur = head
        while cur:
            arr.append(cur.val)
            cur = cur.next

        i, j = 0, len(arr) - 1
        res = 0
        while i < j:
            res = max(res, arr[i] + arr[j])
            i, j = i + 1, j - 1

        return res

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

2. Reverse the Second Half

Intuition

To avoid extra space from converting to an array, we can modify the list itself. Using the slow and fast pointer technique, we find the middle of the list. Then we reverse the second half in place. Now the first half and the reversed second half can be traversed simultaneously, allowing us to compute twin sums directly without extra storage.

Algorithm

Use slow and fast pointers to find the start of the second half. When fast reaches the end, slow is at the midpoint.
Reverse the second half of the list starting from slow.
Initialize first at the head and second at the head of the reversed second half.
While second is not null:
- Compute first.val + second.val and update res if larger.
- Advance both first and second.
Return res.

# 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:
        slow, fast = head, head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

        prev, cur = None, slow
        while cur:
            nxt = cur.next
            cur.next = prev
            prev = cur
            cur = nxt

        res = 0
        first, second = head, prev
        while second:
            res = max(res, first.val + second.val)
            first, second = first.next, second.next

        return res

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$ extra space.

3. Reverse the First Half

Intuition

Instead of reversing the second half after finding the middle, we can reverse the first half as we go. While traversing with slow and fast pointers, we reverse the links behind slow. By the time slow reaches the middle, the first half is already reversed. Now slow points to the start of the second half, and prev points to the end of the reversed first half. We can traverse both halves in parallel to find the maximum twin sum.

Algorithm

Initialize slow and fast at head, and prev as null.
While fast and fast.next are not null:
- Move fast two steps ahead.
- Reverse the link: save slow.next, point slow.next to prev, update prev to slow, and move slow forward.
Now prev points to the tail of the reversed first half, and slow points to the head of the second half.
Traverse both halves together, computing twin sums and tracking the maximum.
Return res.

# 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:
        slow, fast = head, head
        prev = None

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

        res = 0
        while slow:
            res = max(res, prev.val + slow.val)
            prev = prev.next
            slow = slow.next

        return res

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$ extra space.

Common Pitfalls

Incorrect Middle Detection with Fast/Slow Pointers

A common mistake is using the wrong loop condition for finding the middle. For this problem, when fast and fast.next are both not null, slow advances. If you use fast.next and fast.next.next, you may stop one node too early or too late, causing incorrect pairing of twin nodes.

Reversing the Wrong Half

When reversing in-place, some developers accidentally reverse the first half when they intended to reverse the second half, or vice versa. This leads to incorrect twin pairings. Ensure you clearly track which portion of the list you are reversing and where the boundary lies after finding the middle.

Losing Track of Pointers During Reversal

While reversing, failing to save the next pointer before modifying cur.next causes you to lose access to the rest of the list. Always store nxt = cur.next before setting cur.next = prev, then advance using the saved reference.