# 0148. Sort List

<https://leetcode.com/problems/sort-list>

## Description

Given the `head` of a linked list, return *the list after sorting it in **ascending order***.

**Example 1:**

![](https://assets.leetcode.com/uploads/2020/09/14/sort_list_1.jpg)

```
**Input:** head = [4,2,1,3]
**Output:** [1,2,3,4]
```

**Example 2:**

![](https://assets.leetcode.com/uploads/2020/09/14/sort_list_2.jpg)

```
**Input:** head = [-1,5,3,4,0]
**Output:** [-1,0,3,4,5]
```

**Example 3:**

```
**Input:** head = []
**Output:** []
```

**Constraints:**

* The number of nodes in the list is in the range `[0, 5 * 104]`.
* `-105 <= Node.val <= 105`

**Follow up:** Can you sort the linked list in `O(n logn)` time and `O(1)` memory (i.e. constant space)?

## ac1: merge sort

```java
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode sortList(ListNode head) {
        // corner cases
        if (head == null || head.next == null) return head;
        // O(nlogn) merge sort, quick sort, heap sort. because of the nature of Linked List, quick sort and heap sort are not applicable because they require calling index.
        //  use merge sort

        // find mid node, 2 pointers
        ListNode mid = findMid(head);

        //divide 2 parts, head and second
        ListNode first = head;
        ListNode second = mid.next;
        mid.next = null;

        //recursive
        first = sortList(first);
        second = sortList(second);

        //conquer: merge 2 sorted parts, dummy node
        ListNode dummy = new ListNode(0);
        ListNode ranger = dummy;
        while (first != null && second != null) {
            if (first.val < second.val) {
                ranger.next = first;
                first = first.next;
            } else {
                ranger.next = second;
                second = second.next;
            }
            ranger = ranger.next;
        }
        if (first == null) ranger.next = second;
        else ranger.next = first;

        return dummy.next;
    }
    private ListNode findMid(ListNode head) {
        ListNode fast = head, slow = head;
        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
}
```