# [LeetCode 148] Sort List

### Question

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

### 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)
int len = 0;
ListNode temp = head;
while (temp != null) {
temp = temp.next;
len ++;
}
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;
}
``````