SortList [source code]

public class SortList {
static
/******************************************************************************/
class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null)
            return head;
        ListNode slow = head, fast = head;
        while (true) {
            if ((fast = fast.next) == null || (fast = fast.next) == null)
                break;
            if ((slow = slow.next) == null)
                break;
        }
        ListNode slow_next = slow.next;
        slow.next = null;
        return merge (sortList (head), sortList (slow_next));
    }

    ListNode merge (ListNode head1, ListNode head2) {
        ListNode dummy = new ListNode (0), res = dummy;
        while (head1 != null && head2 != null) {
            if (head1.val <= head2.val) {
                res.next = head1;
                head1 = head1.next;
                res.next.next = null;
            } else {
                res.next = head2;
                head2 = head2.next;
                res.next.next = null;
            }
            res = res.next;
        }
        if (head1 != null)
            res.next = head1;
        else if (head2 != null)
            res.next = head2;
        return dummy.next;
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        SortList.Solution tester = new SortList.Solution();
        int[][] inputs = {
            {2,1}, {1,2},
            {4,2,1,3}, {1,2,3,4},
            {3,2,4}, {2,3,4},
        };
        for (int i = 0; i < inputs.length / 2; i++) {
            System.out.println (Printer.separator ());
            ListNode head = ListNode.buildListNode (inputs[2 * i]);
            String input_str = ListNode.serialize (head), ans_str = ListNode.serialize (ListNode.buildListNode (inputs[2 * i + 1])), output_str = ListNode.serialize (tester.sortList (head));
            System.out.printf ("%s -> %s, expected: %s\n", 
                input_str, Printer.wrap (output_str, output_str.equals (ans_str) ? 92 : 91), ans_str
            );
        }
    }
}

这个题目基本就是解决了我以前的一个疑惑: Collections.sort是怎么对LinkedList进行sort的; 这里就是让我们自己实现一下了;

题目要求也是很动真格的, 标准的时间复杂度, O(1) space;

因为要求NlogN的复杂度, 估计是用quick sort或者说merge sort的可能性比较大;

正好还不太熟悉这两种sort的区别(毕竟都是divide&conquer的算法). 大概Wiki搜索了一下, 好像msort就是一个单纯依靠index(mid计算)进行一个partition, 而qsort, 则是一个根据大小进行的分段; msort之后需要一个merge也是这个原因;

这题如果用msort, 那么肯定每一个level都要有一个查长度的遍历过程(快慢指针找中点), 但是这个过程用aggregate的方式分析, 复杂度不会超过NlogN(logN个level, 每一个level是N); 所以msort这题是没有什么问题的;

如果用qsort, 可能要做一个partition的操作? 如果是用InPlace的Lomuto partition, 实现起来可能有点麻烦, 不过如果是out of place, 那么就比较简单; 因为是list题目, 所以即使是out of place collect, 最后也不违反O(1)的空间复杂度;

merge sort能做到O(1) space吗? 最后merge的时候, 肯定要分开的两个array才能进行merge? 但是这个可能也不影响空间复杂度: 每次下行之前, 把input都分成两半, 返回上来的时候再merge组合就行了;

另外这题能用recursion吗? 也没有说; 每一个level能不能用dummy? 如果用了这个就是又多加了一个recursion height的空间占用;

偷看了一眼discuss最高解法, 是一个recursion的解法; 下面也有不是recursion的解法; 算了, 刚开始对自己不要太严格, 先写recursion的解法算了; 关于快慢指针找分割点, 一个小的细节:

关键是找到哪一个link来中断;

dummy肯定是不能用的, 这个是heap space, 怎么都洗不掉的;

again, while header不知道怎么写的时候, 就先不写, 先滥用break.

想了一下, merge还是要用一个dummy; 一开始想要让head比较小的一个list作为res, 还用了这个技巧:

        if (head1.val > head2.val)  
            return merge (head2, head1);        // swap to ensure extra assumption: HEAD1 should be res;

大概逻辑是:

但是后面发现没有用, 被这两个case给break掉了:

最后想想, sort本身是不可以用dummy的, 但是merge应该是可以用的, 因为merge不是recursive的;

在放宽了各种限制之后, 实际上并不是一个很难的题目, 但是最后还是超时才做出来, 速度是8ms (41%);

没有editorial;

https://leetcode.com/problems/sort-list/discuss/46714/Java-merge-sort-solution

public class Solution {  

  public ListNode sortList(ListNode head) {  
    if (head == null || head.next == null)  
      return head;  

    // step 1. cut the list to two halves  
    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;  

    // step 2. sort each half  
    ListNode l1 = sortList(head);  
    ListNode l2 = sortList(slow);  

    // step 3. merge l1 and l2  
    return merge(l1, l2);  
  }  

  ListNode merge(ListNode l1, ListNode l2) {  
    ListNode l = new ListNode(0), p = l;  

    while (l1 != null && l2 != null) {  
      if (l1.val < l2.val) {  
        p.next = l1;  
        l1 = l1.next;  
      } else {  
        p.next = l2;  
        l2 = l2.next;  
      }  
      p = p.next;  
    }  

    if (l1 != null)  
      p.next = l1;  

    if (l2 != null)  
      p.next = l2;  

    return l.next;  
  }  

}

找中点这个地方, 我感觉我自己的这个快慢指针写法才是我最熟悉的, 以后就这样写就行了; 另外, 注意看他这里是slow先动, 这样的情况下他最后要break掉的就是slow前面的这个link, 所以他这里还要额外维护一个prev;

merge的写法是基本差不多的, 但是他当把一个node给attach上去到res之后, 他没有把这个node从原来的list里面给detach出来, 看起来好像也没出问题? 不过我觉得还是detach掉比较好, 逻辑比较干净不容易出问题;

I don’t understand why it is constant space complexity? You call merge function log(length) times right? Each time you make a new ListNode l which next property is the returned list. By the way can I do it on l1 without a new listnode?

Since this is a recursion method, the space complexity is O(log(n)) not O(1). I doubt this method pass OJ.

@cqy0118 prev points to the ListNode before slow. If we do slow.next = null then when there are only two elements left, it will be a infinite loop, since slow will always point to the second node and sort(head) will fail to divide the last two nodes and always result in the last two nodes, hence the stack overflow error.

@wei88
You are indeed right, the space complexity is O(logn), because the sortList function is called recursively. Also, a new node is created for each time a merge function is called. Since both merge and sortList are called logn times, the space is O(logn).

第一个观点是对的, recursion确实让最后有一个logN的空间占用, 但是merge里面的这个dummy是不影响的, 因为当前level的recursion退出之后, 这个dummy就会立刻过期被GC;

看来对于recursion的批评还是很多的; 这种东西如果是实际的面试反而好解决, 问一下就行了;

https://leetcode.com/problems/sort-list/discuss/46712/Bottom-to-up(not-recurring)-with-o(1)-space-complextity-and-o(nlgn)-time-complextity

this problem can be easily solved using recurrence and divide-and-conquer. But it consumes program stack to store the recurring function stack frame, actually it consumes o(lgn) space complexity. Recursion use up-to-bottom strategy , why not try the opposite way–bottom-to-up, luckily it works, it only consumes 0(1) space complexity and o(nlgn) time complextity.

// Merge sort use bottom-up policy,   
// so Space Complexity is O(1)  
// Time Complexity is O(NlgN)  
// stable sort  
class Solution {  
public:  
    ListNode *sortList(ListNode *head) {  
        if(!head || !(head->next)) return head;  

        //get the linked list's length  
        ListNode* cur = head;  
        int length = 0;  
        while(cur){  
            length++;  
            cur = cur->next;  
        }  

        ListNode dummy(0);  
        dummy.next = head;  
        ListNode *left, *right, *tail;  
        for(int step = 1; step < length; step <<= 1){  
            cur = dummy.next;  
            tail = &dummy;  
            while(cur){  
                left = cur;  
                right = split(left, step);  
                cur = split(right, step);  
                tail = merge(left, right, tail);  
            }  
        }  
        return dummy.next;  
    }  
private:  
    // Divide the linked list into two lists,  
    // while the first list contains first n ndoes  
    // return the second list's head  
    ListNode* split(ListNode *head, int n){  
        for(int i = 1; head && i < n; i++) head = head->next;  

        if(!head) return NULL;  
        ListNode *second = head->next;  
        head->next = NULL;  
        return second;  
    }  
     // merge the two sorted linked list l1 and l2,  
     // then append the merged sorted linked list to the node head  
     // return the tail of the merged sorted linked list  
    ListNode* merge(ListNode* l1, ListNode* l2, ListNode* head){  
        ListNode *cur = head;  
        while(l1 && l2){  
            if(l1->val > l2->val){  
                cur->next = l2;  
                cur = l2;  
                l2 = l2->next;  
            }  
            else{  
                cur->next = l1;  
                cur = l1;  
                l1 = l1->next;  
            }  
        }  
        cur->next = (l1 ? l1 : l2);  
        while(cur->next) cur = cur->next;  
        return cur;  
    }  
};

实际上这个我是想过的, 因为做题之前Google merge sort的时候, 是看到原来这个是有Bottom-Up的写法的;

最后这个函数的实现果然不是这么trivial, 核心逻辑:

while(cur){  
    left = cur;  
    right = split(left, step);  
    cur = split(right, step);  
    tail = merge(left, right, tail);  
}

这里split和merge两个函数的设计还是很有意思的, 有点类似strtok的设计方式: 该干的事情干完了之后, 把remaining部分的指针返回上来;

这里while的header也是一个讲究, 因为这个算法比较难的部分就是各种Corner Case, 他这里处理的就比较好: 比如step比较大了之后, 可能right就是Null了(step大于整个长度), 或者cur变成了Null(step大于一半的长度); 这种情况下就应该适时停止; 这两种情况的共同特点就是iteration结束的时候, cur会变成Null;

java版本:

public ListNode sortList(ListNode head) {  
    if (head == null || head.next == null) return head;  

    ListNode cur = head;  
    int length = 0;  
    while (cur != null) {  
        cur = cur.next;  
        length++;  
    }  

    ListNode left, right, tail, dummy;  
    for (int step = 1; step < length; step <<= 1) {  
        // NOTE: no need to assign head to dummy.next  
        // dummy node need to be created within for-loop  
        // because the head may change within each merge operation  
        dummy = new ListNode(0);  
        cur = head;  
        tail = dummy;  
        while (cur != null) {  
            left = cur;  
            right = split(left, step);  
            cur = split(right, step);  
            tail = merge(left, right, tail);  
        }  
        head = dummy.next;// update head  
    }  

    return head;  
}  

// divide the list into two linked list.  
// the first list contains n nodes (or all nodes).  
// return the head of the second list (or null)   
private ListNode split(ListNode head, int n) {  
    for (int i = 1; head != null && i < n; i++) {  
        head = head.next;  
    }  
    if (head == null) return null;  
    ListNode second = head.next;  
    head.next = null;  
    return second;  
}  

// merge the two sorted linked list l1 and l2  
// append the result to the list node head  
// return the tail of the merged sorted list  
private ListNode merge(ListNode l1, ListNode l2, ListNode head) {  
    ListNode cur = head;  
    while (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;  
    }  
    if (l1 != null) cur.next = l1;  
    if (l2 != null) cur.next = l2;  
    while (cur.next != null) {  
        cur = cur.next;  
    }  
    return cur;  
}

不过这个人好像是dummy处理的不太好: 不是放在循环外面来处理, 被人喷了;

That is called bottom-up merge sort. It is the reverse procedure of regular merge sort.
Check Princeton’s online CS course on algorithm. It is all there.

submission最优解: 3(99):

class Solution {  
    private ListNode tail;  
    public ListNode sortList(ListNode head) {  
        if (head == null) return null;  
        else if (head.next == null) {  
            tail = head;  
            return head;  
        }  
        ListNode biggerListHead = null;  
        ListNode smallerListHead = null;  
        ListNode equalListHead = head;  
        ListNode node = head.next;  
        head.next = null;  
        while (node != null) {  
            ListNode next = node.next;  
            if (node.val == head.val) {  
                node.next = equalListHead;  
                equalListHead = node;  
            } else if (node.val > head.val) {  
                node.next = biggerListHead;  
                biggerListHead = node;  
            } else {  
                node.next = smallerListHead;  
                smallerListHead = node;                  
            }  
            node = next;  
        }  

        node = head;  
        if (smallerListHead != null) {  
            head = sortList(smallerListHead);  
            tail.next = equalListHead;  
        } else {  
            head = equalListHead;  
        }  
        if (biggerListHead != null) {  
            node.next = sortList(biggerListHead);  
        } else {  
            tail = node;  
        }  
        return head;  
    }  
}

思路还是比较清晰的, 就是一个quick sort实现, 速度果然是够快;

大概的思路是, 维护smaller, equal, bigger三个list, 来partition; 因为是out of place的, 所以实现起来很简单; 注意他一开始就把head给push到equal list的end了; 这个后面有用; 然后partition的时候就是一个正常的倒序增长就是了; pivot是head; 注意, 一开始他就把head给detach出来了;

partition结束之后, equal list肯定不可能是空的; head这个时候是equal list的end, 然后他用node记录这个end, 然后用head来作为最后返回的res;

然后就是针对smaller和bigger两个list的判断, 进行合并就行了; 一个全局指针tail, 用来标记一个DFS traversal的进度, 这个以前也是见过的; 因为这里是一个DFS过程, 所以这个tail(只在leaf位置更新, 不是Null), 在每一个recursive call返回上来的时候, 都是正好是下一个同级的recursive call的prev;

Problem Description

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

Difficulty:Medium
Total Accepted:126.9K
Total Submissions:427.3K
Contributor:LeetCode
Related Topics
linked listsort
Similar Questions
Merge Two Sorted ListsSort ColorsInsertion Sort List