2130. Maximum Twin Sum of a Linked List - Medium

前往題目

想法

• 儲存到arraylist後就可以一組一組看，不過會需要O(n)空間

思路

1. 把list分一半
2. 把後半的指針全部反轉
3. 計算所有組的總和取最大

Code

網友解答

class Solution {
    public int pairSum(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        int res = Integer.MIN_VALUE;
        
        // Find the middle position
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        ListNode nextNode, prev = null;
        // Reverse the second half list
        while (slow != null) {
            nextNode = slow.next;
            // Reverse the arrow, point to the previous node
            slow.next = prev;
            // Move 1 step to the right
            prev = slow;
            slow = nextNode;
        }

        // Calculate all pairs sum
        while (prev != null) {
            res = Math.max(res, head.val + prev.val);
            prev = prev.next;
            head = head.next;
        }

        return res;
    }
}