Solution: Maximum Twin Sum of a Linked List

Statement

In a linked list of even length $n$, the node at position $i$ (0-based indexing) is considered the twin of the node at position $(n-1-i)$ for all $0 ≤ i < n/2$. For example, if $n=4$, node $0$ and node $3$ are twins, and node $1$ and node $2$ are twins. These pairs are the only twins in a linked list of size $4$.

The twin sum is defined as the sum of a node’s value and its twin’s value.

Given the head of a linked list with an even number of nodes, return the maximum twin sum of the linked list.

Constraints:

• The list contains an even number of nodes in the range $[2, 10^3]$.

• $1 \leq$ Node.data $\leq 10^3$

Solution

The main idea behind finding the maximum twin sum in a linked list is to reverse the second half of the list and sum the corresponding values from both halves. The algorithm first locates the middle node using fast and slow pointers to achieve this. Then, it reverses the second half of the linked list, starting from the middle node. After that, it calculates the twin sums by adding the values of the nodes from the start of the list and the reversed second half while keeping track of the maximum sum found so far. Finally, it returns the maximum sum encountered during the traversal.

Using the above intuition, the solution can be implemented as follows:

1. The first step is to find the middle node of the linked list:

   1. Initialize two pointers, slow and fast, at the head of the linked list. The slow pointer will move one node at a time, while the fast pointer will move two nodes at a time.

   2. Iterate through the linked list using these pointers as long as the fast pointer and its next node are not NULL. The slow pointer moves one step, and the fast pointer moves two steps. By the time the fast pointer reaches the end, the slow pointer will be in the middle of the list.

2. The next step is to reverse the second half of the linked list:

   1. Start iterating the linked list from the middle by initializing a pointer, curr, at the node where slow points.

   2. Initialize another pointer prev with NULL.

   3. Continue the loop as long as the curr is not NULL.

   4. Inside the loop, modify the pointers as follows:

      1. First, save curr.next to temp for later use.

      2. Update curr.next to prev.

      3. Update prev to curr.

      4. Update curr to temp.

3. The final step is to find the twin sum for all twin nodes in the linked list:

   1. First, initialize max_sum with $0$ to keep track of the maximum twin sum found so far.

   2. Initialize the curr pointer at the head of the linked list. Due to the reversing algorithm, the prev pointer would already be pointing at the head of the reversed second half.

   3. Iterate through the list until prev reaches NULL.

   4. Find the twin sum inside the loop by adding the data of the curr node and the prev node.

   5. If this sum is greater than max_sum, update max_sum with this sum.

   6. Move both prev and curr pointers forward.

4. Finally, return max_sum as the maximum twin sum of the given linked list.

Let’s look at the following illustration to get a better understanding of the solution: