# LeetCode - Sort list

## Problem statement

Given the `head` of a linked list, return the list after sorting it in ascending order.

Problem statement taken from: https://leetcode.com/problems/sort-list

Example 1:

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

Example 2:

``````Input: head = [-1, 5, 3, 4, 0]
Output: [-1, 0, 3, 4, 5]
``````

Example 3:

``````Input: head = []
Output: []
``````

Constraints:

``````- The number of nodes in the list is in the range [0, 5 * 10^4].
- -10^5 <= Node.val <= 10^5
``````

### Explanation

#### MergeSort Split and Merge linked list

We can use Merge sort followed by Merge two list algorithm. In short we

1. Break the list in the middle
2. Recursively sort the two sub lists
3. Merge the two sub lists

Let's check the algorithm to understand it better.

#### Algorithm

``````// sortList(head)
- if end

- set temp = NULL

- loop while fast != NULL && fast->next != NULL
- set temp = slow
slow = slow->next
fast = fast->next->next
- while end

- set temp->next = NULL

l2 = mergeList(slow)

- return mergeList(l1, l2)

// mergeList(l1, l2)
- set ptr = new ListNode(0)
current = ptr

- loop while l1 != NULL && l2 != NULL
- if l1->val <= l2->val
- current->next = l1
- l1 = l1->next
- else
- current->next = l2
- l2 = l2->next
- if end

- current = current->next
- while end

- if l1 != NULL
- current->next = l1
- l1 = l1->next
- if end

- if l2 != NULL
- current->next = l2
- l2 = l2->next
- if end

- return ptr->next
``````

Let's check out our solutions in C++, Golang, and Javascript.

#### C++ solution

``````class Solution {
public:
ListNode* mergelist(ListNode *l1, ListNode *l2) {
ListNode *ptr = new ListNode(0);
ListNode *current = ptr;

while(l1 != NULL && l2 != NULL) {
if(l1->val <= l2->val) {
current->next = l1;
l1 = l1->next;
} else {
current->next = l2;
l2 = l2->next;
}

current = current->next;
}

if(l1 != NULL) {
current->next = l1;
l1 = l1->next;
}

if(l2 != NULL) {
current->next = l2;
l2 = l2->next;
}

return ptr->next;
}

ListNode *temp = NULL;

while(fast != NULL && fast->next != NULL) {
temp = slow;
slow = slow->next;
fast = fast->next->next;
}

temp->next = NULL;

ListNode* l2 = sortList(slow);

return mergelist(l1, l2);
}
};``````

#### Golang solution

``````func mergeList(l1, l2 *ListNode) *ListNode {
ptr := &ListNode{0, nil}
current := ptr

for l1 != nil && l2 != nil {
if l1.Val <= l2.Val {
current.Next = l1
l1 = l1.Next
} else {
current.Next = l2
l2 = l2.Next
}

current = current.Next
}

if l1 != nil {
current.Next = l1
l1 = l1.Next
}

if l2 != nil {
current.Next = l2
l2 = l2.Next
}

return ptr.Next
}

}

var temp *ListNode

for fast != nil && fast.Next != nil {
temp = slow
slow = slow.Next
fast = fast.Next.Next
}

temp.Next = nil

l2 := sortList(slow)

return mergeList(l1, l2)
}``````

#### JavaScript solution

``````var mergelist = function(l1, l2) {
let ptr = new ListNode(0);
let current = ptr;

while(l1 != null && l2 != null) {
if(l1.val <= l2.val) {
current.next = l1;
l1 = l1.next;
} else {
current.next = l2;
l2 = l2.next;
}

current = current.next;
}

if(l1 != null) {
current.next = l1;
l1 = l1.next;
}

if(l2 != null) {
current.next = l2;
l2 = l2.next;
}

return ptr.next;
}

}

let temp = null;

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

temp.next = null;

let l2 = sortList(slow);

return mergelist(l1, l2);
};``````

The time complexity of the approach is O(n * log(n)). The space complexity is O(log(n)).

#### Dry Run

Let's dry-run our algorithm for a few examples to see how the solution works.

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

head -> 4 -> 2 -> 1 -> 3

false

Step 2: set temp = NULL
slow -> 4
fast -> 4

Step 3: loop while fast != NULL && fast->next != NULL
fast -> 4 && fast->next -> 2
true

temp = slow
temp -> 4

slow = slow->next
slow -> 2

fast = fast->next->next
fast -> 1

loop while fast != NULL && fast->next != NULL
fast -> 1 && fast-next -> 3
false

temp = slow
temp -> 2

slow = slow->next
slow -> 1

fast = fast->next->next
fast -> NULL

loop while fast != NULL && fast->next != NULL
fast = NULL
false

Step 4: temp.next = NULL
temp -> 2

temp = 4 -> 2 -> NULL

head = 4 -> 2 -> NULL

head -> 4 -> 2 -> NULL

false

Step 7: set temp = NULL
slow -> 4
fast -> 4

Step 8: loop while fast != NULL && fast->next != NULL
fast -> 4 && fast->next -> 2
true

temp = slow
temp -> 4

slow = slow->next
slow -> 2

fast = fast->next->next
fast -> NULL

loop while fast != NULL && fast->next != NULL
fast = NULL
false

Step 9: temp.next = NULL
temp -> NULL

temp = 4 -> NULL

true

We rollback to Step 10 and evaluate next line

Step 12:  l2 = sortList(slow)
slow = 2 -> NULL

true

We rollback to Step 12 and evaluate next line

Step 14: return mergelist(l1, l2)
l1 = 4 -> NULL
l2 = 2 -> NULL

// mergelist(l1, l2)

Step 15: ptr = new ListNode(0)
= 0 -> NULL

current = 0 -> NULL

Step 16: loop while l1 != NULL && l2 != NULL
l1 -> 4
l2 -> 2
true

if l1->val <= l2->val
4 <= 2
false
else
current->next = l2
current = 0 -> 2

l2 = l2->next
l2 = NULL

current = current->next
= 2 -> NULL

loop while l1 != NULL && l2 != NULL
l1 -> 4
l2 -> NULL
false

Step 17: if l1 != NULL
4 != NULL
true

current->next = l1
current = 2 -> 4 -> NULL
l1 = l1->next
= NULL

Step 18: if l2 != NULL
NULL != NULL
false

Step 19: ptr->next
ptr = 0 -> 2 -> 4 -> NULL
ptr->next = 2 -> 4 -> NULL

We follow the algorithm for the rest of the list and return the answer as
1->2->3->4->NULL
``````