Insertion Sort List
描述
Sort a linked list using insertion sort.
分析
无
代码
// Insertion Sort List
// 时间复杂度O(n^2)，空间复杂度O(1)
class Solution {
public:
ListNode *insertionSortList(ListNode *head) {
ListNode dummy(INT_MIN);
//dummy.next = head;
for (ListNode *cur = head; cur != nullptr;) {
auto pos = findInsertPos(&dummy, cur->val);
ListNode *tmp = cur->next;
cur->next = pos->next;
pos->next = cur;
cur = tmp;
}
return dummy.next;
}
ListNode* findInsertPos(ListNode *head, int x) {
ListNode *pre = nullptr;
for (ListNode *cur = head; cur != nullptr && cur->val <= x;
pre = cur, cur = cur->next)
;
return pre;
}
};