Published on

[LeetCode 148] Sort List

Problem

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

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

Thoughts

  • Let's try some merge sort~

TypeScript

/**
 * 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;
}

Reference