Reorder List

1package pkg5leetcode.blind75;2 3/*4 * Reorder List | LC 1435 * APPROACH: Find middle, reverse second half, merge alternating.6 * COMPLEXITY: Time O(n), Space O(1)7 */8public class blind75_LC143ReorderList {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 void reorderList(ListNode head) {18        if (head == null || head.next == null) return;19        ListNode slow = head, fast = head;20        while (fast.next != null && fast.next.next != null) {21            slow = slow.next;22            fast = fast.next.next;23        }24        ListNode second = reverse(slow.next);25        slow.next = null;26        ListNode a = head, b = second;27        while (b != null) {28            ListNode an = a.next, bn = b.next;29            a.next = b;30            b.next = an;31            a = an;32            b = bn;33        }34    }35 36    static ListNode reverse(ListNode head) {37        ListNode prev = null, cur = head;38        while (cur != null) {39            ListNode nxt = cur.next;40            cur.next = prev;41            prev = cur;42            cur = nxt;43        }44        return prev;45    }46 47    static ListNode of(int... vals) {48        ListNode dummy = new ListNode(0), cur = dummy;49        for (int v : vals) { cur.next = new ListNode(v); cur = cur.next; }50        return dummy.next;51    }52 53    static int[] toArray(ListNode head) {54        java.util.List<Integer> list = new java.util.ArrayList<>();55        while (head != null) { list.add(head.val); head = head.next; }56        return list.stream().mapToInt(Integer::intValue).toArray();57    }58 59    public static void main(String[] args) {60        ListNode h = of(1, 2, 3, 4);61        reorderList(h);62        check(java.util.Arrays.equals(toArray(h), new int[]{1, 4, 2, 3}), "case1");63        ListNode h2 = of(1, 2);64        reorderList(h2);65        check(java.util.Arrays.equals(toArray(h2), new int[]{1, 2}), "case2");66        System.out.println("all tests passed");67    }68 69    static void check(boolean cond, String name) {70        if (!cond) throw new AssertionError("FAILED: " + name);71        System.out.println("  PASS " + name);72    }73}