Problem

Given a Linked List, Sort it using merge sort.

Examples

Example 1:

Input: head = [4,2,1,3]
Output: [1,2,3,4]

Solution

Method 1 - Recursive

Refer merge sort - Merge Sort Algorithm.

  1. Get the pointer to middle node
  2. Split the list at the middle node
  3. Continue 1 and 2 , till list size is 1 or 2.
  4. Sort the elements in step 3
  5. Merge the sorted list

Now this involves 2 problems - Middle of the linked list Problem and Merge Two Sorted Linked Lists. To split linked list into 2, we can also use: Split Linked List into two halves fractionally given n

Code

Java
public ListNode sortList(ListNode head) {
if (head == null || head.next == null) {
		return head;
	}
	ListNode left = head;
	// note we are not getting mid node, but pointer to mid node
	ListNode prevToMid = getPointerToMidNode(head);
	ListNode right = prevToMid.next;
	prevToMid.next = null;

	left = sortList(left);
	right = sortList(right);
	return mergeIterative(left, right);
}

public ListNode getPointerToMidNode(ListNode head) {
	ListNode fast = head, slow = head, prev = null;

	while (fast != null && fast.next != null) {
		prev = slow;
		slow = slow.next;
		fast = fast.next.next;
	}

	return prev;
}

public ListNode mergeIterative(ListNode l1, ListNode l2) {
	ListNode dummyHead = new ListNode(0);
	ListNode curr = dummyHead;
	while (l1 != null && l2 != null) {
		if (l1.val < l2.val) {
			curr.next = l1;
			l1 = l1.next;
		} else {
			curr.next = l2;
			l2 = l2.next;
		}
		curr = curr.next;
	}
	curr.next = l1 == null ? l2 : l1;
	return dummyHead.next;
}