Published Apr 08, 2022
[
Given the head of a linked list, return the list after sorting it in ascending order.
Input: head = [4,2,1,3]
Output: [1,2,3,4]
Input: head = [-1,5,3,4,0]
Output: [-1,0,3,4,5]
Input: head = []
Output: []
[0, 5 * 10^4].-10^5 <= Node.val <= 10^5/**
* Definition for singly-linked list.
* class ListNode {
* val: number
* next: ListNode | null
* constructor(val?: number, next?: ListNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
* }
*/
function sortList(head: ListNode | null): ListNode | null {
// base case
if(!head || !head.next){
return head;
}
// split the list into two lists
let left: ListNode = head;
let mid: ListNode = getMid(head);
const temp: ListNode = mid.next;
mid.next = null
mid = temp;
// recursion
left = sortList(left);
mid = sortList(mid);
return merge(left, mid)
};
function getMid(head: ListNode): ListNode {
let slow: ListNode = head, fast: ListNode = head.next;
while(fast && fast.next){
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
function merge(list1: ListNode, list2: ListNode): ListNode {
let tail: ListNode = new ListNode();
let dummy: ListNode = tail;
while(list1 && list2){
if(list1.val < list2.val){
tail.next = list1
list1 = list1.next
} else {
tail.next = list2
list2 = list2.next;
}
tail = tail.next
}
if(list1){
tail.next = list1;
}
if(list2){
tail.next = list2;
}
return dummy.next;
}