Sort List

1package pkg5leetcode.top100;2 3/*4 * Sort List | LC 1485 * APPROACH: Merge sort on linked list with middle split.6 * COMPLEXITY: Time O(n log n), Space O(log n)7 */8public class top100_LC148SortList {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 sortList(ListNode head) {18        if (head == null || head.next == null) return head;19        ListNode slow = head, fast = head, prev = null;20        while (fast != null && fast.next != null) {21            prev = slow;22            slow = slow.next;23            fast = fast.next.next;24        }25        prev.next = null;26        ListNode left = sortList(head);27        ListNode right = sortList(slow);28        return merge(left, right);29    }30 31    static ListNode merge(ListNode a, ListNode b) {32        ListNode dummy = new ListNode(0), tail = dummy;33        while (a != null && b != null) {34            if (a.val <= b.val) { tail.next = a; a = a.next; }35            else { tail.next = b; b = b.next; }36            tail = tail.next;37        }38        tail.next = a != null ? a : b;39        return dummy.next;40    }41 42    static ListNode of(int... vals) {43        ListNode dummy = new ListNode(0), cur = dummy;44        for (int v : vals) { cur.next = new ListNode(v); cur = cur.next; }45        return dummy.next;46    }47 48    static int[] toArray(ListNode head) {49        java.util.List<Integer> list = new java.util.ArrayList<>();50        while (head != null) { list.add(head.val); head = head.next; }51        return list.stream().mapToInt(Integer::intValue).toArray();52    }53 54    public static void main(String[] args) {55        check(java.util.Arrays.equals(toArray(sortList(of(4, 2, 1, 3))), new int[]{1, 2, 3, 4}), "case1");56        check(java.util.Arrays.equals(toArray(sortList(of(-1, 5, 3, 4, 0))), new int[]{-1, 0, 3, 4, 5}), "case2");57        System.out.println("all tests passed");58    }59 60    static void check(boolean cond, String name) {61        if (!cond) throw new AssertionError("FAILED: " + name);62        System.out.println("  PASS " + name);63    }64}