Problem

Given a Linked List, Sort it using merge sort.

Examples

Example 1:

1
2

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 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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

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;
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

class Solution:
    class ListNode:
        def __init__(self, val: int = 0, next: Optional['Solution.ListNode'] = None):
            self.val = val
            self.next = next

    def sortList(self, head: Optional['Solution.ListNode']) -> Optional['Solution.ListNode']:
        if not head or not head.next:
            return head

        left = head
        prev_to_mid = self.get_pointer_to_mid_node(head)
        right = prev_to_mid.next
        prev_to_mid.next = None

        left = self.sortList(left)
        right = self.sortList(right)
        return self.merge_iterative(left, right)

    def get_pointer_to_mid_node(self, head: 'Solution.ListNode') -> 'Solution.ListNode':
        fast, slow, prev = head, head, None

        while fast and fast.next:
            prev = slow
            slow = slow.next
            fast = fast.next.next

        return prev

    def merge_iterative(self, l1: Optional['Solution.ListNode'], l2: Optional['Solution.ListNode']) -> Optional['Solution.ListNode']:
        dummy_head = self.ListNode(0)
        curr = dummy_head
        
        while l1 and l2:
            if l1.val < l2.val:
                curr.next = l1
                l1 = l1.next
            else:
                curr.next = l2
                l2 = l2.next
            curr = curr.next
        
        curr.next = l1 if l1 else l2
        return dummy_head.next

Complexity

  • ⏰ Time complexity: O(n log n) because of the divide-and-conquer approach of merge sort.
  • 🧺 Space complexity: O(1) because the sorting is done in place.