Leetcode algorithm 147. insert and sort the linked list

Topic link ：147. Insert and sort the linked list

Ideas

Algorithm ： Insertion sort
data structure ： Linked list
Ideas ： Define a lastSorted The pointer points to the last ordered node , Let me define one more cur The pointer points to the node currently being judged , If the value of the last ordered node is less than the value of the node currently being judged , that lastSorted Pointers and cur Move the pointer back , Otherwise, it means that the current node needs to be inserted forward , So let's define a pre Node refers to the head node , If pre The next node value of is greater than cur Node value , Then we should put cur Insert into pre Just behind the node .

Code

C++

class Solution {
    
public:
    ListNode* insertionSortList(ListNode* head) {
    
        if (head == nullptr) {
    
            return head;
        }

        ListNode *dummyHead = new ListNode(0);
        dummyHead->next = head;
        ListNode *lastSorted = head, *cur = head->next;
        while (cur != nullptr) {
    
            if (lastSorted->val <= cur->val) {
    
                lastSorted = lastSorted->next;
            } else {
    
                ListNode *pre = dummyHead;
                while (pre->next->val <= cur->val) {
    
                    pre = pre->next;
                }
                lastSorted->next = cur->next;
                cur->next = pre->next;
                pre->next = cur;
            }
            cur = lastSorted->next;
        }
        return dummyHead->next;
    }
};