# 148. Sort List

Sort a linked list in O(nlogn) time using constant space complexity

Thoughts:

Equivalent to write a merge-sort in LinkedList

1. Recursively (O(logn) stack space complexity): halve the list by setting fast-slow pointers
2. Iteratively: have two pointer slow, fast, moved by steps a, b to partition the merge list then merge list inside. Repeat the step and shift blocksize value left by 1-bit until no more element left to be merged.

Code: Recursively (java)

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

// step 1. cut the list to two halves

while (fast != null && fast.next != null) {
prev = slow;
slow = slow.next;
fast = fast.next.next;
}

prev.next = null;

// step 2. sort each half
ListNode l2 = sortList(slow);

// step 3. merge l1 and l2
return merge(l1, l2);
}

public ListNode merge (ListNode l1, ListNode l2){
if(l1 == null) return l2;
if(l2 == null) return l1;
// ListNode head = l1.val > l2.val? l2: l1;
if(l1.val > l2.val){
l2 = l2.next;
}else{
l1 = l1.next;
}

while(l1!=null && l2!= null){
if(l1.val > l2.val){
cur.next = l2;
l2 = l2.next;
}else{
cur.next = l1;
l1 = l1.next;
}
cur = cur.next;
}

// deal with the rest nodes
if(l1 != null) cur.next = l1;
if(l2 != null) cur.next = l2;

}
}
``````

Code: Iterative

``````/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
int count_size(ListNode * node){
int n = 0;
while(node!=NULL){
n++;
node = node->next;
}

return n;
}

int blockSize = 1, n = count_size(head), iter_len = 0;
ListNode* dummyHead  = new ListNode (0);
ListNode * next = NULL, *last = NULL, *it = NULL, *slow = NULL, *fast =NULL;

while(blockSize < n){
iter_len = 0;
while(iter_len < n){
int slow_len = min(n - iter_len, blockSize);
int fast_len = min(n - iter_len - slow_len, blockSize);

slow = it;
if(fast_len!=0){
for(int i = 0; i < slow_len - 1; i++) it = it->next;
// reach fast
fast = it -> next;
it -> next = NULL;
it = fast;
// next
for(int i = 0; i < fast_len - 1; i++) it = it->next;
next = it->next;
it->next = NULL;
it = next;
}

while(slow || fast){
if(!fast || (slow && slow->val < fast->val)){
last->next = slow;
last = slow;
slow = slow->next;
}else{
last->next = fast;
last = fast;
fast = fast-> next;
}
}
last->next = NULL;
iter_len += slow_len + fast_len;

}
blockSize <<=1;
}