# Maximum Twin Sum of a Linked List
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximum-twin-sum-of-a-linked-list)
Canonical: https://scaleengineer.com/dsa/problems/maximum-twin-sum-of-a-linked-list
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers)
**Data structures:** Linked List, Stack
**Companies:** [josh technology](https://scaleengineer.com/companies/josh-technology)
---
## Problem
In a linked list of size `n`, where `n` is **even**, the `ith` node (**0-indexed**) of the linked list is known as the **twin** of the `(n-1-i)th` node, if `0 <= i <= (n / 2) - 1`.

* For example, if `n = 4`, then node `0` is the twin of node `3`, and node `1` is the twin of node `2`. These are the only nodes with twins for `n = 4`.

The **twin sum** is defined as the sum of a node and its twin.

Given the `head` of a linked list with even length, return _the **maximum twin sum** of the linked list_.

**Example 1:**

![](https://assets.glich.co/dsa/maximum-twin-sum-of-a-linked-list/image0.png) 

**Input:** head = [5,4,2,1]
**Output:** 6
**Explanation:**
Nodes 0 and 1 are the twins of nodes 3 and 2, respectively. All have twin sum = 6.
There are no other nodes with twins in the linked list.
Thus, the maximum twin sum of the linked list is 6. 

**Example 2:**

![](https://assets.glich.co/dsa/maximum-twin-sum-of-a-linked-list/image1.png) 

**Input:** head = [4,2,2,3]
**Output:** 7
**Explanation:**
The nodes with twins present in this linked list are:
- Node 0 is the twin of node 3 having a twin sum of 4 + 3 = 7.
- Node 1 is the twin of node 2 having a twin sum of 2 + 2 = 4.
Thus, the maximum twin sum of the linked list is max(7, 4) = 7. 

**Example 3:**

![](https://assets.glich.co/dsa/maximum-twin-sum-of-a-linked-list/image2.png) 

**Input:** head = [1,100000]
**Output:** 100001
**Explanation:**
There is only one node with a twin in the linked list having twin sum of 1 + 100000 = 100001.

**Constraints:**

* The number of nodes in the list is an **even** integer in the range `[2, 105]`.
* `1 <= Node.val <= 105`

# Approaches
## Using an Auxiliary Data Structure (ArrayList)
A straightforward approach is to first convert the linked list into a more flexible data structure like an `ArrayList`. By storing all node values in an array, we can easily access any element by its index. This allows us to pair the `i`-th element with the `(n-1-i)`-th element directly.
**Time:** O(n), where n is the number of nodes. The first traversal to populate the list takes O(n) time, and the second pass with two pointers takes O(n/2) = O(n) time. · **Space:** O(n), as we need an `ArrayList` to store the values of all n nodes in the linked list.
**Pros:** Simple to understand and implement.; Does not modify the original linked list structure.
**Cons:** Requires extra space proportional to the size of the linked list, which can be significant for large lists.
### Explanation
First, we iterate through the entire linked list from head to tail. During this traversal, we add the value of each node to an `ArrayList`. After the list is fully traversed, the `ArrayList` contains all the node values in order.

We then use a two-pointer technique on the `ArrayList`. One pointer (`left`) starts at the beginning (index 0), and the other (`right`) starts at the end (index `n-1`). We iterate as long as `left` is less than `right`. In each iteration, we calculate the sum of the values at the `left` and `right` indices, which corresponds to a twin sum. We keep track of the maximum sum found so far. After each sum calculation, we move the pointers closer to the center (`left++`, `right--`). The loop terminates when the pointers meet or cross, at which point we have checked all twin pairs. The maximum sum recorded is the result.

```java
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public int pairSum(ListNode head) {
        java.util.List<Integer> values = new java.util.ArrayList<>();
        ListNode current = head;
        while (current != null) {
            values.add(current.val);
            current = current.next;
        }

        int left = 0;
        int right = values.size() - 1;
        int maxTwinSum = 0;

        while (left < right) {
            int currentSum = values.get(left) + values.get(right);
            maxTwinSum = Math.max(maxTwinSum, currentSum);
            left++;
            right--;
        }

        return maxTwinSum;
    }
}
```
### Algorithm
- Create an empty `java.util.ArrayList<Integer>` to store the node values.
- Traverse the linked list from the `head`, adding each node's value to the `ArrayList`.
- Initialize a variable `maxTwinSum` to 0.
- Initialize two pointers, `left = 0` and `right = list.size() - 1`.
- Loop while `left < right`:
  - a. Calculate `currentSum = list.get(left) + list.get(right)`.
  - b. Update `maxTwinSum = Math.max(maxTwinSum, currentSum)`.
  - c. Increment `left` and decrement `right`.
- Return `maxTwinSum`.

## Reversing the Second Half of the Linked List
A more space-efficient approach involves reversing the second half of the linked list in-place. This allows us to traverse the first half and the (reversed) second half simultaneously to find the twin sums without using extra storage.
**Time:** O(n). Finding the middle takes O(n), reversing the second half takes O(n), and calculating the sums takes O(n). The total time complexity is linear. · **Space:** O(1). This approach only uses a constant amount of extra space for pointers, regardless of the list's size.
**Pros:** Highly space-efficient, using only constant extra space.; Optimal solution for this problem.
**Cons:** More complex to implement than the ArrayList approach.; Modifies the structure of the original linked list. (Though it could be restored with another reversal pass if needed).
### Explanation
This method consists of three main steps:

1.  **Find the middle:** We use the classic "slow and fast pointer" technique. The `slow` pointer moves one step at a time, while the `fast` pointer moves two steps. When the `fast` pointer reaches the end of the list, the `slow` pointer will be at the beginning of the second half.
2.  **Reverse the second half:** Starting from the node indicated by the `slow` pointer, we reverse the remainder of the list. This creates a new, reversed sub-list representing the second half.
3.  **Calculate twin sums:** We now have two pointers: one at the original `head` of the list (`p1`) and another at the head of the reversed second half (`p2`). We iterate through both halves, summing `p1.val` and `p2.val` at each step. We keep track of the maximum sum encountered. Since both halves have `n/2` nodes, the loop runs `n/2` times.

This approach cleverly manipulates the list's pointers to achieve the goal with constant extra space.

```java
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public int pairSum(ListNode head) {
        // 1. Find the middle of the linked list
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        // 2. Reverse the second half of the list
        ListNode secondHalfHead = reverseList(slow);

        // 3. Calculate twin sums
        ListNode p1 = head;
        ListNode p2 = secondHalfHead;
        int maxTwinSum = 0;
        while (p2 != null) {
            int currentSum = p1.val + p2.val;
            maxTwinSum = Math.max(maxTwinSum, currentSum);
            p1 = p1.next;
            p2 = p2.next;
        }

        return maxTwinSum;
    }

    private ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode current = head;
        while (current != null) {
            ListNode nextNode = current.next;
            current.next = prev;
            prev = current;
            current = nextNode;
        }
        return prev;
    }
}
```
### Algorithm
- Use two pointers, `slow` and `fast`, both starting at `head`.
- Move `slow` one step and `fast` two steps at a time until `fast` reaches the end of the list. `slow` will now be at the middle.
- Reverse the linked list starting from `slow`. Let the head of this new reversed list be `secondHalfHead`.
- Initialize `maxTwinSum` to 0.
- Initialize a pointer `firstHalfHead` to the original `head`.
- Iterate while `secondHalfHead` is not null:
  - a. Calculate `currentSum = firstHalfHead.val + secondHalfHead.val`.
  - b. Update `maxTwinSum = Math.max(maxTwinSum, currentSum)`.
  - c. Move both pointers forward: `firstHalfHead = firstHalfHead.next` and `secondHalfHead = secondHalfHead.next`.
- Return `maxTwinSum`.

# Solutions
### Java

```java
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public int pairSum ( ListNode head ) { List < Integer > s = new ArrayList <>(); for (; head != null ; head = head . next ) { s . add ( head . val ); } int ans = 0 , n = s . size (); for ( int i = 0 ; i < ( n >> 1 ); ++ i ) { ans = Math . max ( ans , s . get ( i ) + s . get ( n - 1 - i )); } return ans ; } }
```

### CPP

```cpp
/** * 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 ) { vector < int > s ; for (; head != nullptr ; head = head -> next ) s . push_back ( head -> val ); int ans = 0 , n = s . size (); for ( int i = 0 ; i < ( n >> 1 ); ++ i ) ans = max ( ans , s [ i ] + s [ n - i - 1 ]); return ans ; } };
```

### Python

```python
# 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 : s = [] while head : s . append ( head . val ) head = head . next n = len ( s ) return max ( s [ i ] + s [ - ( i + 1 )] for i in range ( n >> 1 ))
```