148. Sort List

[Tcdian]

148. Sort List

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

Follow up: Can you sort the linked list in O(n logn) time and O(1) memory (i.e. constant space)?

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 * 104].
• -105 <= Node.val <= 105

[Tcdian]

Solution

• TypeScript Solution

/**
 * 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 {
    if (head === null || head.next === null) {
        return head;
    }
    let guard: ListNode | null = new ListNode(-1, head);
    let slow: ListNode | null = guard;
    let fast: ListNode | null = guard;
    while(fast !== null && fast.next !== null) {
        fast = fast.next.next;
        slow = slow!.next;
    }
    const rightList = slow!.next;
    slow!.next = null;
    const leftList = guard.next;
    let leftSorted = sortList(leftList);
    let rightSorted = sortList(rightList);
    guard.next = null;
    let patrol = guard;
    while (leftSorted !== null && rightSorted !== null) {
        if (leftSorted.val <= rightSorted.val) {
            patrol.next = leftSorted;
            leftSorted = leftSorted.next;
        } else {
            patrol.next = rightSorted;
            rightSorted = rightSorted.next;
        }
        patrol = patrol.next;
        patrol.next = null;
    }
    patrol.next = leftSorted || rightSorted;
    return guard.next;
};