/** * 这题采用merge sort，可自顶向下或自底向上 * 区别是自顶向下是递归的，需要额外的空间 * 而自底向上不用 * 时间复杂度都是O(nlgn) */ public class SortList { /** * 自顶向下 */ public ListNode sortList(ListNode head) { if (head == null || head.next == null) return head; ListNode prev = null, slow = head, fast = head; while (fast != null && fast.next != null) { prev = slow; slow = slow.next; fast = fast.next.next; } prev.next = null; ListNode l1 = sortList(head); ListNode l2 = sortList(slow); return merge(l1, l2); } ListNode merge(ListNode l1, ListNode l2) { ListNode dummy = new ListNode(0), cur = dummy; for ( ; l1 != null && l2 != null; ) { if (l1.val < l2.val) { cur.next = l1; l1 = l1.next; } else { cur.next = l2; l2 = l2.next; } cur = cur.next; } cur.next = l1 != null ? l1 : l2; return dummy.next; } /** * 自底向上 */ public ListNode sortList2(ListNode head) { int size = 0; for (ListNode node = head; node != null; node = node.next, size++); ListNode dummy = new ListNode(0); ListNode left, right, cur, tail; for (int step = 1; step <= size; step *= 2) { for (cur = head, tail = dummy; cur != null; ) { left = cur; right = split(left, step); cur = split(right, step); tail = merge(left, right, tail); } head = dummy.next; } return dummy.next; } /** * 将l1和l2合并后挂在tail下，返回新的tail */ ListNode merge(ListNode l1, ListNode l2, ListNode tail) { for ( ; l1 != null && l2 != null; ) { if (l1.val < l2.val) { tail.next = l1; l1 = l1.next; } else { tail.next = l2; l2 = l2.next; } tail = tail.next; } tail.next = l1 != null ? l1 : l2; for ( ; tail.next != null; tail = tail.next); return tail; } /** * 从start开始取step个节点，返回下一个节点 */ private ListNode split(ListNode start, int step) { for (step--; start != null && step > 0; step--, start = start.next); if (start != null && start.next != null) { ListNode next = start.next; start.next = null; return next; } return null; } }