[Leetcode Solution] Sort List

Great Problem

Analysis

• Quick sort and merge sort are acceptable whose time complexity is O(nlogn)

Note

• First use Quick Sort. Program runs well but last test case exceeds time limit. What suddenly hit my mind is that average time complexity of both Quick sort and Merge sort are O(nlogn). The worst case complexity for merge sort is still O(nlogn). Quick sort however is O(n^2). 

• From this respect merge sort seems better then Quick sort then why Quick sort is more widely used. In piratical when in memory sort is performed, Quick sort can take more advantage of memory locality. It is also a in-place algorithm which means less memory is needed.

• No matter what kind of sort method is used, it won't be constant space complexity if use recursive function. 

• How to merge two linkded list in order. If INT_MAX is used to represent the edge value. Attention should be paid that what if some input data is INT_MAX and what will happen

Code in Quick Sort

Code in Merge Sort 

Updated at LeetCode 2th Pass
Using recursive solution would be kind of easy because function stacks store all the node information automatically. 
However recursive solution won't use only constant memory. Thus we use the iterative way that merge the linked list from bottom to top.
Note

1. How to find the mid node of a linked list
2. Attention must be paid that when manipulate a sub list in place, the edge between previous node to the first node and the edge between last node to behind node must take care.

Code in Merge Sort IN CONSTANT MEMORY