Daily algorithms – Linked lists

Insert sort on linked lists

Insert sort on linked lists

Analysis of the

  1. During traversal, the write pointer points to the largest value before the current list, so when the read pointer reads something less than the write pointer, it needs to delete and insert
  2. First, the write pointer is the pointer that precedes read, so it’s easy to delete the current read pointer
  3. And then you find the insertion point, and if it’s a bidirectional pointer, you can look from the end to the front, or you can look from the head
  4. Start at the start head node to find a node larger than the current read pointer value, and insert before it
  5. And you end up with a linked list
  6. Iterate over and over in traversal, time should be 0(nlogn)0(nlogn)0(nlogn)
// 147. Insert sort into linked lists
// https://leetcode-cn.com/problems/insertion-sort-list/

var insertionSortList = function(head) {
    if(! head || ! head.next)return head
    let  emptyNode = new ListNode()
    emptyNode.next = head
    let  write = head
    let read =write.next
    while(read){
        if(read.val<write.val){
            / / delete first
            let next = read.next
            write.next = next

            // Start with the empty pointer to find the position to insert
            let prev = emptyNode
            let temp = emptyNode.next
            while(temp.val<=read.val){
                temp = temp.next
                prev = prev.next
            }
            // Insert before temp
            prev.next = read
            read.next = temp
            read = next
        }else{
            read = read.next
            write=write.next
        }
    }
    return emptyNode.next
};
Copy the code

This article is participating in the “Nuggets 2021 Spring Recruitment Campaign”, click to see the details of the campaign