148. Sort List

yPhantom 2019年10月14日 31次浏览

Sort a linked list in O(n log n) time using constant space complexity.

Example 1:

Input: 4->2->1->3
Output: 1->2->3->4

Example 2:

Input: -1->5->3->4->0
Output: -1->0->3->4->5

Solution

题目要求用O(nlogn)的时间复杂度,可以想到归并排序,但是O(1)的空间复杂度,那么就不能用递归了。

参考DISCUSS

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode sortList(ListNode head) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        boolean isDone = head == null;
        ListNode[] subList = new ListNode[2];
        for(int step = 1; !isDone; step *= 2) {
            isDone = true;
            ListNode prev = dummy;
            ListNode remaining = prev.next;
            while (remaining != null) {
                // Split off two sublists of size step
                for (int i = 0; i < 2; i++) {
                    subList[i] = remaining;
                    ListNode tail = null;
                    for(int j = 0; j < step && remaining != null; j++, remaining = remaining.next) {
                        tail = remaining;
                    }
                    if (tail != null) {
                        tail.next = null;
                    }
                }
                // merge
                if (subList[1] == null) {
                    prev.next = subList[0];
                } else {
                    while (subList[0] != null || subList[1] != null) {
                        int idx = (subList[1] == null || subList[0] != null && subList[0].val < subList[1].val) ? 0 : 1;
                        prev.next = subList[idx];
                        subList[idx] = subList[idx].next;
                        prev = prev.next;
                    }
                    prev.next = null;
                }
                isDone &= remaining == null;
            }
        }
        return dummy.next;
    }
}

顺便附上递归的实现吧,递归的话空间复杂度就不是O(1)了。