> For the complete documentation index, see [llms.txt](https://junnie.gitbook.io/amazon-mock-interview/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://junnie.gitbook.io/amazon-mock-interview/2022/oa/linkedlistsum.md).

# LinkedListSum

https\://leetcode.com/discuss/interview-question/1546673/Amazon-or-OA-or-LinkedListSum

```
Give a linked list, which has even number of nodes, please return the maximum sum of PAIR
A pair means the node[i] and node[n-i], which n is linked list length.
example: [1,2,3,4,9,11]
1st pair sum: 1 + 11 = 13
2nd pair sum: 2 + 9 = 11
3rd pair sum: 3 + 4 = 7
Therefore, return 13

Please note that, you can only solve it with space complexity O(1)
```

**Solution:**

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

Same as <https://leetcode.com/problems/maximum-twin-sum-of-a-linked-list/>