### Can you sort a Linked List in `O(nlogn)` time using constant space complexity?

``````Given 4->2->1->3, sort it to 1->2->3->4.

Given -1->5->3->4->0, sort it to -1->0->3->4->5.
``````

Let's see the solution first and we will go over it later.

``````	public ListNode sortList(ListNode head) {

// step 1. get the middle node
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}

// get the head of second list

// break the first list
slow.next = null;

// step 2. sort the two lists

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

ListNode dummy = new ListNode(0);
ListNode prev = dummy;

} else {
}
prev = prev.next;
}

} else {
}

return dummy.next;
}

``````

You can break the solution into these parts:

1. find the middle node using slow and fast node
2. break the list into halves
3. sort and merge the lists

That's is it! You might find the concept very similar to the Linked List questions that we have done before. For example, find the middle node using slow/fast pointers, reverse linked list and etc. Once you get the idea of it, you will be able to master linked list very soon! See you next time!

Post was published on , last updated on .

Like the content? Support the author by paypal.me!