主題
題目連結：
題目意譯：
在一個長度為 n 的連結串列（Linked List）中，其中 n 為一偶數，第 i 個節點（索引值從 0 開始）與第 (n - 1 - i) 個節點是成對的，如果 0 ≦ i ≦ (n / 2) - 1。
例如如果 n = 4，則節點 0 與節點 3 是成對的，而節點 1 與節點 2 成對。這些正好是 n = 4 時僅有的成對節點。
成對和則定義為一個節點與其成對者之總和。
給定一個偶數長度的連結串列之開頭 head，回傳串列中最大之成對和。
限制：
串列中的節點數量為一位於範圍 [2, 10 ^ 5] 中的偶數。
1 ≦ Node.val ≦ 10 ^ 5
範例測資：
範例 1：
輸入： head = [5,4,2,1]
輸出： 6
解釋：
節點 0 和 1 依序與節點 3 和 2 成對。每對都有著成對和 = 6。
連結串列中沒有其他的成對節點。
因此連結串列中最大的成對和為 6。
範例 2：
輸入： head = [4,2,2,3]
輸出： 7
解釋：
連結串列中成對節點如下：
- 節點 0 與節點 3 成對，並有著成對和 4 + 3 = 7。
- 節點 1 與節點 2 成對，並有著成對和 2 + 2 = 4。
因此連結串列中最大的成對和為 max(7, 4) = 7。
範例 3：
輸入： head = [1,100000]
輸出： 100001
解釋：
連結串列中只有一個成對和，其為一節點與其成對者之和為 1 + 100000 = 100001。
解題思維：
由於連結串列不支援隨機存取（Random Access，又稱直接存取（Direct Access）），也就是從節點 i 到節點 n - 1 - i，我們必須從節點 i →節點 i + 1 →……一路到節點 n - 1 - i。
而如果我們對於每對節點都這樣子存取的話，時間將會是 O(n ^ 2)，其中 n 為節點數。
因此我們有以下作法：
方法一：
直接掃過一次連結串列的內容，然後將其複製到一個長度也是 n 的陣列上。而陣列支援隨機存取，因此我們只需要 O(n) 掃過一次陣列便可以掃過所有成對的節點，便可以找到其中最大的成對和。
方法二：
一樣掃過一次連結串列，然後複製一份一模一樣的新串列出來。然後將這個串列利用這題的方式反轉節點的順序。之後我們便可以看到現在這同樣的索引值在兩個串列上便是成對的。因此我們便可以同時掃過原始串列、反轉後的新串列而得到所有的成對和並得到所求最大值。
方法三：
上述兩個方法都需要 O(n) 的額外空間，那有沒有只需要 O(1) 額外空間的？答案是有的。
在方法二中可以看到反轉順序後的原串列與原串列本身的節點一一對應後即是題目定義的成對節點。那實際上如果我們可以把原串列拆成兩半，然後把後面那一半反轉順序不就可以成對了？而這就是本方法的核心。
因此我們可以利用這題找到後面那一半的開頭（而且可以順便得到整個串列的長度之一半），然後將這一半按照上面的方式反轉。不過因為我們在這邊沒有特別斷開前半與後半，因此反轉的流程應只執行到中間便需停止（也就是只把後面 n / 2 個節點的指標反轉，前面的則保留原樣）。
最後同時掃一次這兩半即可得到所求。
最後，以上三個方法的時間複雜度皆為 O(n)。因此讀者可以挑自己喜歡的實作即可。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
