“This is the first day of my participation in the First Challenge 2022. For details: First Challenge 2022”

148. Sort linked lists

Given the head of your list, please sort it in ascending order and return the sorted list. Example 1:

Input: head = [4,2,1,3] output: [1,2,3,4]Copy the code

Example 2:

Input: head = [-1,5,3,4,0]Copy the code

Example 3:

Input: head = [] Output: []Copy the code

Tip:

  • The number of nodes in the linked list is in range[0, 5 * 104] 内
  • -105 <= Node.val <= 105

Merge sort

The more efficient thought sorting algorithm such as merge, fast, bucket sorting time complexity is Nlogn, suitable for linked list sorting is merge sort.

So let’s do this with the idea of merging two ways

First we need to divide the linked list into two parts, left and right. We can use fast and slow Pointers

Then, the left is recursively processed respectively. The termination condition of recursion is that head is a single node, and the right is recursively processed to get sorted sortLeft and sortRight

Finally merge sortLeft and sortRight to get the final result and return it

The specific implementation

  • Return if head is null or head. Next is null
  • Through the fast and slow pointer, the fast pointer fast takes two steps at a time, i.e. fast.next-next, and the slow pointer takes one step, slow. Next.

The left section starts at the beginning of the list and the right section starts at slow.next. And interrupts from solw.next=null

  • Recursively processing left and right produces two sorted sublists
  • Merge two lists, provided that both lists still have values. If one list has been completely merged, the remaining sub-lists are directly joined
  • Finally, the result of the merge is returned
var sortList = function (head) {
    // Termination conditions
    if(! head || ! head.next) {return head
    }
    // The fast and slow Pointers find the midpoint
    var newHead = new ListNode(0, head)
    var fast = newHead
    var slow = newHead
    while (fast && fast.next) {
        fast = fast.next.next
        slow = slow.next
    }

    var right = slow.next
    slow.next = null
    var left = newHead.next

    // Process sublists recursively
    var sortLeft = sortList(left)
    var sortRight = sortList(right)
    // Merge sorted sublists
    var sortNewHead = new ListNode(0)
    var curr = sortNewHead
    while (sortLeft && sortRight) {
        if (sortLeft.val < sortRight.val) {
            curr.next = sortLeft
            sortLeft = sortLeft.next
        } else {
            curr.next = sortRight
            sortRight = sortRight.next
        }
        curr = curr.next
    }
    if (sortRight) {
        curr.next = sortRight
    }
    if (sortLeft) {
        curr.next = sortLeft
    }
    return sortNewHead.next

};
Copy the code