Leetcode- insert and sort the linked list

Topic content

Sample analysis

Code implementation

    public ListNode insertionSortList(ListNode head) {
        if(head == null) return null;
        ListNode newHead = new ListNode(0);
        newHead.next = head;
        ListNode SortedLast = head;
        ListNode cur = SortedLast.next;
        while(cur != null) {
            if(SortedLast.val <= cur.val) {
                SortedLast = SortedLast.next;
                // Continue to judge the next node to be sorted 
                cur = SortedLast.next;
            } else {
                // Get into else It means to insert it in front 
                ListNode prev = newHead;
                while(prev.next.val <= cur.val) {
                    prev = prev.next;
                }
                // The successor of the last data in the ordered sequence is bound to the next data to be sorted 
                SortedLast.next = cur.next;
                // The successor of the inserted element is bound with the data after it in the ordered sequence 
                cur.next = prev.next;
                // The subsequent data of the previous inserted element is bound to the inserted element 
                prev.next = cur;
                // Continue to judge the next node to be sorted 
                cur = SortedLast.next;
            }
        }
        return newHead.next;
    }

Analyze the connection with the arrangement

  Key step analysis

When we adjust the order of nodes , First the SortedLast The next element to be sorted , The linked list has two fields , I'm used to tying the back first , Reprocess the successor of the previous element .

 

Analyze the above figure 1,2,3 Code for ：

1. The successor of the last element of an ordered sequence is always bound to the first element of the sequence to be sorted , Cyclic advance else, Indicates that the value of the element to be inserted is less than SortedLast, So put SortedLast The successor of is bound to the next element to be inserted .

2. Whether you enter or not while loop ,prev The value of the position of must be just less than cur Value ,while The function of circulation is to adjust prev The point is just less than cur The previous node of the value of the node .

3. hold prev The successor tied the plug-in cur, To form an orderly sequence .

  Complexity analysis

1. Time complexity

The sorting of linked lists is not like arrays , There is no need to move the data , Just change the direction , But because the linked list has no so-called subscript , So the time complexity required to find the subscript of the insertion position is O(n) ,n A sort of data , So the time complexity is O(n^2).

2. Spatial complexity   O(1)

This is the end of this article. ！！！