Maximum Twin Sum of a Linked List

How it works

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.

Steps

1. Initialize slow and fast at head, and prev as null.
2. 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.
3. Now prev points to the tail of the reversed first half, and slow points to the head of the second half.
4. Traverse both halves together, computing twin sums and tracking the maximum.
5. Return res.

Complexity

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

Things to watch for

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.

from typing import Optional

# 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

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    int pairSum(ListNode* head) {
        ListNode* slow = head, *fast = head, *prev = nullptr;

        while (fast && fast->next) {
            fast = fast->next->next;
            ListNode* tmp = slow->next;
            slow->next = prev;
            prev = slow;
            slow = tmp;
        }

        int res = 0;
        while (slow) {
            res = max(res, prev->val + slow->val);
            prev = prev->next;
            slow = slow->next;
        }

        return res;
    }
};