# 2130. Maximum Twin Sum of a Linked List (M)

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*.

&#x20;

**Example 1:**

![](https://assets.leetcode.com/uploads/2021/12/03/eg1drawio.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.leetcode.com/uploads/2021/12/03/eg2drawio.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.leetcode.com/uploads/2021/12/03/eg3drawio.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.
```

&#x20;

**Constraints:**

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

### Solution:

<https://leetcode.com/discuss/interview-question/1546673/Amazon-or-OA-or-LinkedListSum>\
step 1 : count the number of nodes in the list - O(N) time\
step 2 : break the list from middle and reverse the second half of linked list - O(N) time and O(1) space if we ignore recursion\
step 3 : after step 2 above, the lists would be like 1-->4 and 2-->3\
now, this is as good as traversing two lists simultaneously and computing the sums and checking for max - O(N) time

step 4 : if needed, restore the structure of the linked list back - O(N) time again

```
class Solution {
    public int pairSum(ListNode head) {
        
        ListNode slow = head;
        ListNode fast = head;
        while(fast != null && fast.next != null)
        {
            slow = slow.next;
            fast = fast.next.next;
        }
        
        ListNode first = head;
        ListNode second = reverse(slow);
        int result = Integer.MIN_VALUE;
        while(first != null && second != null)
        {
            result = Math.max(result, first.val + second.val);
            first = first.next;
            second = second.next;
        }
        
        return result;
    }
    
    
    //Reverse the LinkedList
    public ListNode reverse(ListNode head)
    {
        if(head == null && head.next != null)
        {
            return head;
        }
        
        ListNode prev = null; 
        ListNode current = head;
        while(current != null)
        {
            ListNode post = current.next;
            current.next = prev;
            prev = current;
            current = post;
        }
        return prev;
    }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://junnie.gitbook.io/nine-chapter/5.linkedlist/2130.-maximum-twin-sum-of-a-linked-list-m.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.