[Leetcode] Sort List

Problem

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

Algorithm

Quick sort needs swap nodes in pairs, which is not easy in a singly linked list. 

Recursive merge sort is not constant space, as shown in code 1. It leads to Stack Overflow Error. 

In-place merge sort of linked list is shown in code. In the code, two sorted sublists needs to be merged. Left sublist start with left head and end with leftTail, right sublist start with rightHead and rightTail. PreTail is the tail of the previous sublist, and postHead is the head of the post sublist.

First, we locate all the nodes, including preTail, leftHead, leftTail, rightHead, rightTail and postHead. Second, If rightHead == null, no need to merge. Else, cut at the leftTail and rightTail.
Third,  merge the two sorted sublist left and right.
Four, connect preTail to merged head, and merged tail to postHead.

Made a mistake at line 27, i.e. how to determine the tail of merged list.

Code