Maximum Twin Sum of a Linked List

1package pkg5leetcode.official75;2 3/*4 * Maximum Twin Sum of a Linked List | LC 21305 * APPROACH: Find mid, reverse second half, max pair sum.6 * COMPLEXITY: Time O(n), Space O(1)7 */8public class official75_LC2130MaximumTwinSumOfALinkedList {9    /** Same shape as pkg5leetcode/common/ListNode.java (nested for single-file runs). */10 11    static class ListNode {12        int val;13        ListNode next;14        ListNode(int val) { this.val = val; }15    }16 17    static int pairSum(ListNode head) {18        ListNode slow = head, fast = head;19        while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; }20        ListNode second = reverse(slow);21        int best = 0;22        ListNode a = head, b = second;23        while (b != null) {24            best = Math.max(best, a.val + b.val);25            a = a.next; b = b.next;26        }27        return best;28    }29 30    static ListNode reverse(ListNode head) {31        ListNode prev = null, cur = head;32        while (cur != null) {33            ListNode n = cur.next; cur.next = prev; prev = cur; cur = n;34        }35        return prev;36    }37 38    public static void main(String[] args) {39        ListNode h = new ListNode(5); h.next = new ListNode(4); h.next.next = new ListNode(2);40        h.next.next.next = new ListNode(1);41        check(pairSum(h) == 6, "case1");42        ListNode h2 = new ListNode(4); h2.next = new ListNode(2); h2.next.next = new ListNode(4);43        h2.next.next.next = new ListNode(3);44        check(pairSum(h2) == 7, "case2");45        System.out.println("all tests passed");46    }47 48    static void check(boolean cond, String name) {49        if (!cond) throw new AssertionError("FAILED: " + name);50        System.out.println("  PASS " + name);51    }52}