Question

link

Stats

Adjusted Difficulty	4
Time to use	--------

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Analysis

This is a difficult question.

To sort with O(nlgn) time, we must use either quick sort or merge sort.

Solution

This is a standard merge sort algorithm. The details can be found here.

I am being lazy here, I reused the code from “Merge Two Sorted Lists”. Surprisingly it worked! Just remember, we must set the last node of first half to point to null.

Code

public ListNode sortList(ListNode head) {
    if (head == null || head.next == null) 
        return head;
    int len = 0;
    ListNode temp = head;
    while (temp != null) {
        temp = temp.next;
        len ++;
    }
    temp = head;
    for (int i = 1; i < len / 2; i ++)
        temp = temp.next;
    ListNode firstHalf = head, secondHalf = temp.next;
    temp.next = null;
    return mergeTwoLists(sortList(firstHalf), 
                         sortList(secondHalf));
}

// The following code is copied from
// Question - Merge Two Sorted Lists
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    ListNode pre = new ListNode(Integer.MIN_VALUE);
    ListNode cur = pre;
    while (l1 != null && l2 != null) {
        if (l1.val < l2.val) {
            cur.next = l1;
            l1 = l1.next;
        } else {
            cur.next = l2;
            l2 = l2.next;
        }
        cur = cur.next;
    }
    if (l1 == null) cur.next = l2;
    else cur.next = l1;
    return pre.next;
}