Partition List

1package pkg5leetcode.top100;2 3/*4 * Partition List | LC 865 * APPROACH: Two dummy lists for <x and >=x; concatenate.6 * COMPLEXITY: Time O(n), Space O(1)7 */8public class top100_LC86PartitionList {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 ListNode partition(ListNode head, int x) {18        ListNode before = new ListNode(0), after = new ListNode(0);19        ListNode b = before, a = after;20        while (head != null) {21            if (head.val < x) { b.next = head; b = b.next; }22            else { a.next = head; a = a.next; }23            head = head.next;24        }25        a.next = null;26        b.next = after.next;27        return before.next;28    }29 30    static ListNode of(int... vals) {31        ListNode dummy = new ListNode(0), cur = dummy;32        for (int v : vals) { cur.next = new ListNode(v); cur = cur.next; }33        return dummy.next;34    }35 36    static int[] toArray(ListNode head) {37        java.util.List<Integer> list = new java.util.ArrayList<>();38        while (head != null) { list.add(head.val); head = head.next; }39        return list.stream().mapToInt(Integer::intValue).toArray();40    }41 42    public static void main(String[] args) {43        check(java.util.Arrays.equals(toArray(partition(of(1, 4, 3, 2, 5, 2), 3)), new int[]{1, 2, 2, 4, 3, 5}), "case1");44        check(java.util.Arrays.equals(toArray(partition(of(2, 1), 2)), new int[]{1, 2}), "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}