Task

Sort a linked list using insertion sort.

leetcode147

A graphical example of insertion sort. The partial sorted list (black) initially contains only the first element in the list. With each iteration one element (red) is removed from the input data and inserted in-place into the sorted list

Algorithm of Insertion Sort:

  1. Insertion sort iterates, consuming one input element each repetition, and growing a sorted output list.
  2. At each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there.
  3. It repeats until no input elements remain.

Example

  • Example 1:
1
2

Input: 4->2->1->3
Output: 1->2->3->4
  • Example 2:
1
2

Input: -1->5->3->4->0
Output: -1->0->3->4->5

Solution

  • 建立dummy便于快速定位到开头
  • 使用3个指针：prev、curr、tmp
    • 若curr比下一个节点小，则直接移动curr
    • 若curr比下一个节点大，准备将下一个节点换到前面：
      • tmp是curr的下一个节点（准备插入到前面的节点）
      • 让prev从dummy开始向后移动，直到找到最后一个小于tmp的节点（tmp的目的位置）
      • 交换指针，将tmp换到正确的位置
  • 时间复杂度：插入排序，每查找一个元素应该属于的位置需遍历前面是O(n)，故总复杂度是O(n^2)
  • 空间复杂度：仅用了dummy节点和3个指针，O(1)
  • 实现：
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

// Runtime: 16 ms, faster than 95.09% of C++ online submissions for Insertion Sort List.
// Memory Usage: 8.8 MB, less than 100.00% of C++ online submissions for Insertion Sort List.
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* insertionSortList(ListNode* head) {
        ListNode *dummy=new ListNode(0,head);
        ListNode *prev=nullptr,*cur=head,*tmp=nullptr;
        while(cur && (cur->next)){
            if(cur->val <= cur->next->val)
                cur=cur->next;
            else{
                tmp=cur->next;
                prev=dummy;
                while(prev->next->val <= tmp->val)
                    prev=prev->next;
                cur->next=tmp->next;
                tmp->next=prev->next;
                prev->next=tmp;
            }
        }
        return dummy->next;
    }
};