148. Sort List

Key idea: partition sort = find middle + sort left and right + merge(left, right)

核心： 分段排序 ＝ 找中间节点 ＋ 排序左边，排序右边 ＋ 合并左右两部分

English

Dummy node (When the head is not determinated)

• remove duplicates from Sorted List 1&2

• Merge two sorted list

• Partition list

• Reverse list

Chinese

When doing merge to two lists and don't know the head, we define dummy node = new Node(0), head, then head = dummy, return dummy.next at last.

在合并两个list并且还不知道头节点的时候，我们先定义一个虚拟节点并初始化，和一个当前节点（当前指针），然后让当前指针指向虚拟节点，最后完成合并后返回dummy.next。

Java

class Solution {
    public ListNode sortList(ListNode head) {
        // stop condition
        if(head == null || head.next == null)
            return head;
        
        // find middle
        ListNode fast = head.next, slow = head;
        while(fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        // sort two parts
        ListNode head2 = slow.next;
        slow.next = null;
        ListNode first = sortList(head);
        ListNode second = sortList(head2);
        //combine two parts
        ListNode dump = new ListNode();
        ListNode temp = dump;
        while(first != null && second != null) {
            if(first.val < second.val) {
                temp.next = first;
                first = first.next;
            } else {
                temp.next = second;
                second = second.next;
            }
            temp = temp.next;
        }
        if(first != null)
            temp.next = first;
        if(second != null)
            temp.next = second;
        
        return dump.next;
    }
}

Python

T = O(n lgn), lgn  层调用，每层都做find middle 和 merge需要O(n), S = O(lgn), length of stack.