Leetcode 連結

這題可以用反轉鏈結串列（reverse linked list）的技巧來解。
如果你還沒解過 Leetcode 206，建議先去練習，熟悉如何反轉單向鏈結串列。

Input: head = [4,2,2,3]
Output: 7

由於孿生和（twin sum）的定義是：從頭數來第 i 個節點與從尾數來第 i 個節點相加（串列長度為偶數），我們可以反轉鏈結串列來模擬從尾端存取節點。

原始串列: [4, 2, 2, 3]
反轉後: [3, 2, 2, 4]

接著同時依序走訪兩個串列，計算每一組配對的和。
在這個例子中，我們比較：

4 + 3 = 7
2 + 2 = 4
2 + 2 = 4
3 + 4 = 7

所以最大孿生和是 7。

由於在 Java 中無法直接複製鏈結串列，需要手動複製。以下是我寫的輔助函式：

public ListNode copyList(ListNode head) {
    if (head == null) return null;

    ListNode newHead = new ListNode(head.val);
    ListNode currOld = head.next;
    ListNode currNew = newHead;

    while (currOld != null) {
        currNew.next = new ListNode(currOld.val);
        currNew = currNew.next;
        currOld = currOld.next;
    }

    return newHead;
}

我們建立原始鏈結串列的兩份副本：

  • 一份維持原本順序
  • 一份反轉

接著同時走訪兩個串列，逐步計算孿生和。

還有一個可以優化的地方：因為孿生配對是對稱的，其實只需要走訪到串列的一半即可。
另外也可以用快慢指針找到原始串列的中點，只反轉後半段，再計算孿生和（空間效率更好）。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public int pairSum(ListNode head) {
        ListNode tempNode = copyList(head);
        ListNode curr = copyList(head);
        ListNode rev = reverseNode(tempNode);
        int max = 0;
        while (curr != null && rev != null) {
            int temp = curr.val + rev.val;
            if (temp > max) {
                max = temp;
            }
            curr = curr.next;
            rev = rev.next;
        }
        return max;
    }

    public ListNode reverseNode(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }

    public ListNode copyList(ListNode head) {
        if (head == null) return null;

        ListNode newHead = new ListNode(head.val);
        ListNode currOld = head.next;
        ListNode currNew = newHead;

        while (currOld != null) {
            currNew.next = new ListNode(currOld.val);
            currNew = currNew.next;
            currOld = currOld.next;
        }

        return newHead;
    }

}