---

What is Twin Sum?

In a linked list of even length, twin sum is the sum of pairs formed by:

• The first and last node

• The second and second-last node

• …and so on, until all nodes are paired.

✨ Example:

Consider the linked list: 1 -> 3 -> 4 -> 5 -> NULL

The twin pairs are: (1,5) and (3,4)

Now, the maximum twin sum is max(1 + 5, 3 + 4) = max(6, 7) = 7.

---

Problem:

Given a singly linked list like:
1 -> 3 -> 4 -> 5 -> NULL

• Find the maximum twin sum among all twin node pairs.

Output:
7 (because 3 + 4 = 7 > 1 + 5 = 6)

---

Challenge with Singly Linked List:

Unlike arrays:

• We cannot directly access the last node using an index.

• We cannot move backward; only forward traversal is possible.

👉 Reason:
In a singly linked list, each node only knows about its next node — not the previous one.

---

Intuition:

To mimic the "two-pointer" technique in a singly linked list:

• Break the list into two halves:

  • One half is from the head to just before the middle node.

  • The other half is from the last node to the middle node (after reversing).

How?

• Find the middle of the list using slow and fast pointers.

• Reverse the second half of the list.

• Now, we can easily pair the nodes from both halves and calculate twin sums.

---

Step-by-Step Approach:

1. Find the Middle Node

Use the classic slow and fast pointer method:

• slow moves one step at a time, like this: slow = slow->next.

• fast moves two steps at a time, like this: fast = fast->next->next.

When fast reaches the end, slow will be at the middle.

Example:
For 1 -> 3 -> 4 -> 5 -> NULL, slow will point to 4 (middle node).

---

2. Reverse the Second Half

Once the middle is found:

• Start from the middle node and reverse the remaining part of the list.

Visual after reversing:

• First half: 1 -> 3

• Second half (after reversal): 5 -> 4

---

3. Calculate the Maximum Twin Sum

Now:

• Initialize two pointers:

  🔹 firstHead → Head of the first half,

• 🔹 secondHead → Head of the reversed second half.

• Move both pointers simultaneously while calculating the sum of their corresponding node values.

• Update the twin sum whenever you find a greater value, using the max function.

while (secondHead) {
    maxTwinSum = max(maxTwinSum, firstHead->val + secondHead->val);
    firstHead = firstHead->next;
    secondHead = secondHead->next;
}

---

Final Code:

/**
 * 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) {
        // Step 1: Find the middle node
        ListNode *slow = head;
        ListNode *fast = head;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
        }

        // Step 2: Reverse the second half
        ListNode *prev = nullptr;
        ListNode *curr = slow;
        while (curr) {
            ListNode *next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }

        // Step 3: Find the maximum twin sum
        int maxTwinSum = 0;
        ListNode *first = head;
        ListNode *second = prev;
        while (second) {
            maxTwinSum = max(maxTwinSum, first->val + second->val);
            first = first->next;
            second = second->next;
        }

        return maxTwinSum;
    }
};

---

🔥 Complexities:

Time Complexity: O(N)

• Finding the middle node → O(N/2)

• Reversing the second half → O(N/2)

• Traversing to find the maximum twin sum → O(N/2)

Thus, overall time complexity = O(N)

---

Space Complexity: O(1)

• We are only using a few pointers (slow, fast, prev, curr, first, second).

• No extra data structures or arrays are used.

Thus, overall space complexity = O(1)

---

🏁 Keep coding, keep optimizing! 🚀

---