C++ | Leetcode C++题解之第147题对链表进行插入排序

题目：

题解：

class Solution {
public:ListNode* insertionSortList(ListNode* head) {if (head == nullptr) {return head;}ListNode* dummyHead = new ListNode(0);dummyHead->next = head;ListNode* lastSorted = head;ListNode* curr = head->next;while (curr != nullptr) {if (lastSorted->val <= curr->val) {lastSorted = lastSorted->next;} else {ListNode *prev = dummyHead;while (prev->next->val <= curr->val) {prev = prev->next;}lastSorted->next = curr->next;curr->next = prev->next;prev->next = curr;}curr = lastSorted->next;}return dummyHead->next;}
};