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

虚拟节点（当头节点不确定时）

• 在已排序的list里删除重复节点1和2

• 合并两个list

• 分段排序list

• 反转list

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

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def sortList(self, head: ListNode) -> ListNode:
        # edge case
        if head == None or head.next == None:
            return head
        
        # find middle
        mid = self.findMid(head)
        head2 = mid.next
        mid.next = None
        
        # sort list
        left = self.sortList(head)
        right = self.sortList(head2)
        
        # merge list
        return self.merge(left, right)
        
    def findMid(self, head):
        fast = head.next
        slow = head
        while fast != None and fast.next != None:
            fast = fast.next.next
            slow = slow.next
        return slow
    
    def merge(self, head1, head2):
        dummy = ListNode(0)
        temp = dummy

        while head1 != None and head2 != None:
            if head1.val < head2.val:
                temp.next = head1
                head1 = head1.next
            else:
                temp.next = head2
                head2 = head2.next
            temp = temp.next
        
        if head1 == None:
            temp.next = head2
        else:
            temp.next = head1
        
        return dummy.next

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