Insertion Sort List

描述

Sort a linked list using insertion sort.

分析

无

代码

  1. // Insertion Sort List
  2. // 时间复杂度O(n^2)，空间复杂度O(1)
  3. class Solution {
  4. public:
  5.     ListNode *insertionSortList(ListNode *head) {
  6.         ListNode dummy(INT_MIN);
  7.         //dummy.next = head;
  9.         for (ListNode *cur = head; cur != nullptr;) {
  10.             auto pos = findInsertPos(&dummy, cur->val);
  11.             ListNode *tmp = cur->next;
  12.             cur->next = pos->next;
  13.             pos->next = cur;
  14.             cur = tmp;
  15.         }
  16.         return dummy.next;
  17.     }
  19.     ListNode* findInsertPos(ListNode *head, int x) {
  20.         ListNode *pre = nullptr;
  21.         for (ListNode *cur = head; cur != nullptr && cur->val <= x;
  22.             pre = cur, cur = cur->next)
  23.             ;
  24.         return pre;
  25.     }
  26. };

相关题目

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/cpp/sorting/insertion-sort/insertion-sort-list.html