# Question

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

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

Example 1:

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


Example 2:

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)?

# 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.

# Code

• 
public class Sort_List {

public class Solution {
/**
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/

ListNode dummy = new ListNode(0);

ListNode prev = dummy;

// 每次都要找中点，复杂度略高啊
while (fast != null && fast.next != null) {
prev = slow;
slow = slow.next;
fast = fast.next.next;
}

ListNode left = head; // eg. [1,2]
ListNode right = slow;
prev.next = null; // cut

ListNode sortedLeft = sortList(left);
ListNode sortedRight = sortList(right);

return mergeSorted(sortedLeft, sortedRight);
}

public ListNode mergeSorted(ListNode left, ListNode right) {
ListNode dummy = new ListNode(0);

ListNode current = dummy;

while (left != null || right != null) {
int lval = left == null ? Integer.MAX_VALUE : left.val;
int rval = right == null ? Integer.MAX_VALUE : right.val;

if (lval < rval) {
current.next = new ListNode(lval);
left = left.next; // I missed this...
} else {
current.next = new ListNode(rval);
right = right.next;
}

current = current.next;
}

return dummy.next;
}
}

// constant extra space using Bottom Up Approach
class Solution_bottom_up_merge_sort {
ListNode tail = new ListNode(0);
ListNode nextSubList = new ListNode(0);

for (int size = 1; size < n; size = size * 2) {
while (start != null) {
if (start.next == null) {
tail.next = start;
break;
}
ListNode mid = split(start, size);
merge(start, mid);
start = nextSubList;
}
}
}

ListNode split(ListNode start, int size) {
ListNode midPrev = start;
ListNode end = start.next;
//use fast and slow approach to find middle and end of second linked list
for (int index = 1; index < size && (midPrev.next != null || end.next != null); index++) {
if (end.next != null) {
end = (end.next.next != null) ? end.next.next : end.next;
}
if (midPrev.next != null) {
midPrev = midPrev.next;
}
}
ListNode mid = midPrev.next;
midPrev.next = null;
nextSubList = end.next;
end.next = null;
// return the start of second linked list
return mid;
}

void merge(ListNode list1, ListNode list2) {
while (list1 != null && list2 != null) {
if (list1.val < list2.val) {
newTail.next = list1;
list1 = list1.next;
newTail = newTail.next;
} else {
newTail.next = list2;
list2 = list2.next;
newTail = newTail.next;
}
}
newTail.next = (list1 != null) ? list1 : list2;
// traverse till the end of merged list to get the newTail
while (newTail.next != null) {
newTail = newTail.next;
}
// update the old tail to the new tail of merged list
tail = newTail;
}

int cnt = 0;
while (ptr != null) {
ptr = ptr.next;
cnt++;
}
return cnt;
}
}

}

############

/**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode() {}
*     ListNode(int val) { this.val = val; }
*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
}
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
ListNode t = slow.next;
slow.next = null;
ListNode l2 = sortList(t);
ListNode dummy = new ListNode();
ListNode cur = dummy;
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) {
cur.next = l1;
l1 = l1.next;
} else {
cur.next = l2;
l2 = l2.next;
}
cur = cur.next;
}
cur.next = l1 == null ? l2 : l1;
return dummy.next;
}
}

• // OJ: https://leetcode.com/problems/sort-list/
// Time: O(NlogN)
// Space: O(logN)
class Solution {
ListNode dummy, *p = &dummy, *q = &dummy;
while (q && q->next) {
q = q->next->next;
p = p->next;
}
auto next = p->next;
p->next = NULL;
return next;
}
ListNode *mergeList(ListNode *a, ListNode *b) {
while (a && b) {
ListNode *node;
if (a->val <= b->val) {
node = a;
a = a->next;
} else {
node = b;
b = b->next;
}
tail->next = node;
tail = node;
}
if (a) tail->next = a;
if (b) tail->next = b;
}
public:
}
};

• # 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:
while fast and fast.next:
slow, fast = slow.next, fast.next.next
t = slow.next
slow.next = None
dummy = ListNode()
cur = dummy
while l1 and l2:
if l1.val <= l2.val:
cur.next = l1
l1 = l1.next
else:
cur.next = l2
l2 = l2.next
cur = cur.next
cur.next = l1 or l2
return dummy.next

############

# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
"""
:rtype: ListNode
"""
pre = None

while fast and fast.next:
pre = slow
slow = slow.next
fast = fast.next.next

if not pre:
pre.next = None

right = self.sortList(slow)

p = dummy = ListNode(-1)
while left and right:
if left.val < right.val:
p.next = left
left = left.next
else:
p.next = right
right = right.next
p = p.next

if left:
p.next = left
if right:
p.next = right
return dummy.next


• /**
* type ListNode struct {
*     Val int
*     Next *ListNode
* }
*/
}
for fast != nil && fast.Next != nil {
slow, fast = slow.Next, fast.Next.Next
}
t := slow.Next
slow.Next = nil
dummy := &ListNode{}
cur := dummy
for l1 != nil && l2 != nil {
if l1.Val <= l2.Val {
cur.Next = l1
l1 = l1.Next
} else {
cur.Next = l2
l2 = l2.Next
}
cur = cur.Next
}
if l1 != nil {
cur.Next = l1
} else {
cur.Next = l2
}
return dummy.Next
}

• /**
* class ListNode {
*     val: number
*     next: ListNode | null
*     constructor(val?: number, next?: ListNode | null) {
*         this.val = (val===undefined ? 0 : val)
*         this.next = (next===undefined ? null : next)
*     }
* }
*/

function sortList(head: ListNode | null): ListNode | null {
// 快慢指针定位中点
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
// 归并排序
let mid: ListNode = slow.next;
slow.next = null;
let l2: ListNode = sortList(mid);
let dummy: ListNode = new ListNode();
let cur: ListNode = dummy;
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) {
cur.next = l1;
l1 = l1.next;
} else {
cur.next = l2;
l2 = l2.next;
}
cur = cur.next;
}
cur.next = l1 == null ? l2 : l1;
return dummy.next;
}


• /**
* function ListNode(val, next) {
*     this.val = (val===undefined ? 0 : val)
*     this.next = (next===undefined ? null : next)
* }
*/
/**
* @return {ListNode}
*/
var sortList = function (head) {
}
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
}
let t = slow.next;
slow.next = null;
let l2 = sortList(t);
const dummy = new ListNode();
let cur = dummy;
while (l1 && l2) {
if (l1.val <= l2.val) {
cur.next = l1;
l1 = l1.next;
} else {
cur.next = l2;
l2 = l2.next;
}
cur = cur.next;
}
cur.next = l1 || l2;
return dummy.next;
};


• /**
* public class ListNode {
*     public int val;
*     public ListNode next;
*     public ListNode(int val=0, ListNode next=null) {
*         this.val = val;
*         this.next = next;
*     }
* }
*/
public class Solution {
{
}
while (fast != null && fast.next != null)
{
slow = slow.next;
fast = fast.next.next;
}
ListNode t = slow.next;
slow.next = null;
ListNode l2 = SortList(t);
ListNode dummy = new ListNode();
ListNode cur = dummy;
while (l1 != null && l2 != null)
{
if (l1.val <= l2.val)
{
cur.next = l1;
l1 = l1.next;
}
else
{
cur.next = l2;
l2 = l2.next;
}
cur = cur.next;
}
cur.next = l1 == null ? l2 : l1;
return dummy.next;
}
}

• // Definition for singly-linked list.
// #[derive(PartialEq, Eq, Clone, Debug)]
// pub struct ListNode {
//   pub val: i32,
//   pub next: Option<Box<ListNode>>
// }
//
// impl ListNode {
//   #[inline]
//   fn new(val: i32) -> Self {
//     ListNode {
//       next: None,
//       val
//     }
//   }
// }
impl Solution {
pub fn sort_list(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
fn merge(l1: Option<Box<ListNode>>, l2: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
match (l1, l2) {
(None, Some(node)) | (Some(node), None) => Some(node),
(Some(mut node1), Some(mut node2)) => {
if node1.val < node2.val {
node1.next = merge(node1.next.take(), Some(node2));
Some(node1)
} else {
node2.next = merge(Some(node1), node2.next.take());
Some(node2)
}
}
_ => None,
}
}

fn sort(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
}
let mut length = 0;
while cur.is_some() {
length += 1;
cur = &cur.as_ref().unwrap().next;
}
let mut cur = &mut head;
for _ in 0..(length / 2 - 1) {
cur = &mut cur.as_mut().unwrap().next;
}
let right = cur.as_mut().unwrap().next.take();