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)

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
  public ListNode sortList(ListNode head) {
    if (head == null || head.next == null)
      return head;

    // step 1. cut the list to two halves
    ListNode prev = null, slow = head, fast = head;

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

    prev.next = null;

    // step 2. sort each half
    ListNode l1 = sortList(head);
    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;
        ListNode head;
        if(l1.val > l2.val){
            head = l2;
            l2 = l2.next;
        }else{
            head = l1;
            l1 = l1.next;
        }

        ListNode cur = head;

        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;

        return head;
    }
}

Code: Iterative

/**
 * Definition for singly-linked list.
 * 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;
    }

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

        while(blockSize < n){
            iter_len = 0;
            last = dummyHead;
            it = dummyHead -> next;
            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;
        }

        return dummyHead -> next;
    }
};