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) {
		if (head == null || head.next == null)
			return head;

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

        // get the head of second list
		ListNode newHead = slow.next;
        
        // break the first list
		slow.next = null;

		// step 2. sort the two lists
		ListNode l1 = sortList(head);
		ListNode l2 = sortList(newHead);

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

	private ListNode merge(ListNode head1, ListNode head2) {

		ListNode dummy = new ListNode(0);
		ListNode prev = dummy;
		while (head1 != null && head2 != null) {

			if (head1.val < head2.val) {
				prev.next = head1;
				head1 = head1.next;
			} else {
				prev.next = head2;
				head2 = head2.next;
			}
			prev = prev.next;
		}

		if (head1 != null) {
			prev.next = head1;
		} else {
			prev.next = head2;
		}

		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 1 Feb 2020, last updated on 1 Feb 2020.

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