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/