> For the complete documentation index, see [llms.txt](https://r24zeng.gitbook.io/leetcode-notebook/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://r24zeng.gitbook.io/leetcode-notebook/wan-quan-an-zhao-jiu-zhang-suan-fa-shua-de-60-dao-zuo-you/vi.-linked-list/148.-sort-list.md).

# 148. Sort List

{% hint style="success" %}

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

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

{% endhint %}

{% tabs %}
{% tab title="English" %}

#### Dummy node (When the head is not determinated)

* remove duplicates from Sorted List 1&2
* Merge two sorted list
* Partition list
* Reverse list
  {% endtab %}

{% tab title="Chinese" %}

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

* 在已排序的list里删除重复节点1和2
* 合并两个list
* 分段排序list
* 反转list
  {% endtab %}
  {% endtabs %}

{% hint style="danger" %}
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`。
{% endhint %}

{% tabs %}
{% tab title="Java" %}

```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;
    }
}
```

{% endtab %}

{% tab title="Python" %}

```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
```

{% endtab %}
{% endtabs %}

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