文章作者：Tyan
博客：noahsnail.com | CSDN | 简书
1. Description
Insertion Sort List
2. Solution
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* insertionSortList(ListNode* head) {
if(!head || !head->next) {
return head;
}
ListNode* list = head;
ListNode* current = head->next;
ListNode* next = nullptr;
head->next = nullptr;
while(current != nullptr) {
next = current->next;
list = insert(list, current);
current = next;
}
return list;
}
private:
ListNode* insert(ListNode* head, ListNode* node) {
node->next = nullptr;
if(head->val >= node->val) {
node->next = head;
return node;
}
ListNode* pre = head;
ListNode* current = head->next;
while(current) {
if(current->val > node->val) {
break;
}
pre = current;
current = current->next;
}
pre->next = node;
node->next = current;
return head;
}
};
