LeetCode: Sort List

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

---

We can use merge sort to sort linked list. Split the list into single elements and merge them recursively.

C++ Code:

/*
 * func: merge_sort_list
 * goal: merge two sorted list into one
 * @param left_part: one sorted linked list
 * @param right_part: another sorted linked list
 * return: new head after merge
 */
ListNode *merge_sort_list(ListNode *left_part, ListNode *right_part){
    ListNode *left_iter = left_part;
    ListNode *right_iter = right_part;
    ListNode *new_head = nullptr;
    ListNode *new_iter = nullptr;
    while(left_iter && right_iter){
        ListNode *curr = nullptr;
        if(left_iter->val >= right_iter->val){
            curr = right_iter;
            right_iter = right_iter->next;
        }else{
            curr = left_iter;
            left_iter = left_iter->next;
        }
        
        if(new_head == nullptr){
            new_head = curr;
            new_iter = curr;
        }else{
            new_iter->next = curr;
            new_iter = new_iter->next;
        }
    }
    
    if(left_iter){
        if(new_head == nullptr){
            new_head = left_iter;
            new_iter = left_iter;
        }else{
            new_iter->next = left_iter;
            new_iter = new_iter->next;
        }
    }
    
    if(right_iter){
        if(new_head == nullptr){
            new_head = right_iter;
            new_iter = right_iter;
        }else{
            new_iter->next = right_iter;
            new_iter = new_iter->next;
        }
    }
    
    return new_head;
}
/*
 * func: sort_list
 * goal: sort the list in o(n logn) times
 * @param head: head node of the list
 * return: new head
 */
ListNode *sort_list(ListNode *head){
    ListNode *slow = head;
    ListNode *fast = head;
    while(fast->next && fast->next->next){
        slow = slow->next;
        fast = fast->next->next;
    }
    ListNode *right = slow->next;
    slow->next = nullptr;
    ListNode *left_part = sort_list(head);
    ListNode *right_part = sort_list(right);
    ListNode *new_head = merge_sort_list(left_part, right_part);
    return new_head;
}

Python Code:

# func: merge sort for linked list
# @param head: start sorting node
# @param length: length of the list to be sorted
# return: new head
def merge_sort_list(head, length):
    if length == 0 or length == 1:
        return head

    prev = head
    for _ in xrange(length/2 - 1):
        prev = prev.next

    curr = prev.next
    prev.next = None
    left_part = merge_sort_list(head, length/2)
    right_part = merge_sort_list(curr, length - length/2)

    left_iter = left_part
    right_iter = right_part
    new_head = None
    new_iter = None

    while left_iter and right_iter:
        if left_iter.val >= right_iter.val:
            curr = right_iter
            right_iter = right_iter.next
        else:
            curr = left_iter
            left_iter = left_iter.next

        if not new_head:
            new_head = curr
            new_iter = curr
        else:
            new_iter.next = curr
            new_iter = new_iter.next

    if left_iter:
        if not new_head:
            new_head = left_iter
        else:
            new_iter.next = left_iter

    if right_iter:
        if not new_head:
            new_head = right_iter
        else:
            new_iter.next = right_iter
    return new_head

# func: sort link list in O(n logn)
# @param root: head node
# @return: new head node
def sort_list(head):
    length = 0
    iter = head
    while iter:
        length += 1
        iter = iter.next

    return merge_sort_list(head, length)