# 2130. Maximum Twin Sum of a Linked List
###### tags: `Leetcode` `Medium` `Linked List`
Link: https://leetcode.com/problems/maximum-twin-sum-of-a-linked-list/description/
## 思路
### 思路一 $O(N)$ $O(1)$
首先用快慢指针找到linked list的中点
接着reverse 中点及它后面的node
然后两个指针一个从head开始扫 一个从reverse过的linked list的起点开始扫 两个一起移动 每次移动都是一个新的twin sum
### 思路二 $O(N)$ $O(N)$
先扫一遍linked list 然后用map存每个index的value
接着扫map 找到答案
## Code
$O(N)$ $O(1)$

class Solution {
    public ListNode reverseLinkedList(ListNode head){
        ListNode prev = null;
        ListNode curr = head;
        ListNode next;
        while(curr!=null){
            next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
    public int pairSum(ListNode head) {
        int ans = 0;
        ListNode slow = head, fast = head;
        while(fast!=null && fast.next!=null){
            slow = slow.next;
            fast = fast.next.next;
        }
        slow = reverseLinkedList(slow);
        while(head!=null && slow!=null){
            ans = Math.max(ans, head.val+slow.val);
            head = head.next;
            slow = slow.next;
        }
        return ans;
    }
}

$O(N)$ $O(N)$

class Solution {
    public int pairSum(ListNode head) {
        int curIdx = 0;
        Map<Integer, Integer> map = new HashMap<>();
        int ans = 0;
        while(head!=null){
            map.put(curIdx, head.val);
            curIdx++;
            head = head.next;
        }
        //the length of linked list is now equal to curIdx
        for(int i=0; i<curIdx; i++){
            ans = Math.max(ans, map.get(i)+map.get(curIdx-i-1));
        }
        return ans;
    }
}