# Question

Formatted question description: https://leetcode.ca/all/148.html

148. Sort List

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

Example 1:

Input: 4->2->1->3
Output: 1->2->3->4

Example 2:

Input: -1->5->3->4->0
Output: -1->0->3->4->5



# Algorithm

The title limits the time to be O(nlgn). Only

• quick sort,
• merge sort, and
• heap sort meet the requirements. According to the characteristics of singly linked lists, merge sort is most suitable.

To do merge sort, the middle node of the list should be found. Use two pointers to find the middle node. Each time the fast pointer moves two steps and the slow pointer moves one step. When the fast pointer moves to the end, the slow pointer points the middle node. After finding the middle node, do merge sort for two parts of the node respectively, and merge the two parts after both parts are sorted.

Two merge two parts of a list, always find the node with the smallest number each time and append the node to the sorted list.

Java