Subject to introduce

Force buckle 147: leetcode-cn.com/problems/in…

Analysis of the

The basic idea of insertion sort is to maintain an ordered sequence with only one element at the beginning. Each time a new element is inserted into the ordered sequence, the length of the ordered sequence increases by 1 until all elements are added to the ordered sequence.

If it is an insertion sort of an array, the first part of the array is an ordered sequence. Each time the insertion position of the first element after the ordered sequence (the element to be inserted) is found, the element after the insertion position in the ordered sequence is moved back one bit, and then the element to be inserted is placed in the insertion position.

For the linked list, when inserting an element, it only needs to update the pointer of the adjacent node, and there is no need to move the element after the insertion position backward like array. Therefore, the time complexity of the insertion operation is O(1), but finding the insertion position requires traversing the nodes in the linked list, and the time complexity is O(n). So the total time complexity of list insertion sort is still O(n^2), where n is the length of the list.

For a unidirectional list, there is only a pointer to the next node, so you need to start from the head node of the list and traverse the nodes in the list to find the insertion location.

The procedure for inserting a linked list is as follows.

• First, determine whether the given linked list is empty. If it is empty, it does not need to sort and returns directly.

• Create dumb node dummyHead and set dummyHead. Next = head. Dummy nodes are introduced to facilitate inserting nodes before head nodes.

• Maintains lastSorted as the last node of the sorted part of the list, originally lastSorted = head.

• Maintains curr as the element to be inserted, initially curr = head.next.

• Compare the node values of lastSorted and curr.

  • If lastSorted. Val <= curr.val, curr should come after lastSorted. Move lastSorted one bit later, and curr becomes the new lastSorted.

  • Otherwise, start at the head of the list and traverse the nodes in the list backwards to find where to insert the curr. Set prev to the previous node where the curr was inserted, and do the following to complete the insertion of the curr:

lastSorted.next = curr.next
curr.next = prev.next
prev.next = curr
Copy the code

• Leave curr = lastSorted. Next, where curr is the next element to be inserted.

• Repeat steps 5 and 6 until curr becomes empty and the sorting ends.

• Return dummyHead. Next as the head node of the sorted list.

The code is as follows:

class Solution {
    public ListNode insertionSortList(ListNode head) {
        // 1. Check whether the given list is empty, if it is empty, no sorting is required, and return directly.
        if(head == null) {return head;
        }

        // 2. Initialize the list
        ListNode dummyHead = new ListNode(0); // Introduce dummy nodes
        dummyHead.next = head;                // The purpose is to insert the node before head
        ListNode lastSorted = head;           // maintain lastSorted as the lastSorted node of the linked list and initialize it
        ListNode curr = head.next;            // Maintain curr as the element to be inserted and initialize

        // 3. Insert sort
        while(curr ! =null) {if(lastSorted.val <= curr.val){     // Curr should come after lastSorted
                lastSorted = lastSorted.next;   // Move lastSorted back one bit. Curr becomes the new lastSorted
            }else{                              Otherwise, the nodes in the list are traversed backwards from the list header
                ListNode prev = dummyHead;      Prev is the node before the curr position of the node is inserted
                while(prev.next.val <= curr.val){ // The condition for loop exit is to find where curr should be inserted
                    prev = prev.next;
                }
                // The following three lines are used to insert the curr.
                lastSorted.next = curr.next;
                curr.next = prev.next;
                prev.next = curr;
            }
            curr = lastSorted.next; // Curr is the next element to be inserted
        }
        // Return the sorted list
        returndummyHead.next; }}Copy the code

Complexity analysis

• Time complexity: O(n^2), where n is the length of the list.
• Space complexity: O(1).