147、Insertion Sort List

Sort a linked list using insertion sort.

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 1:

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

Example 2:

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

思路

直接插入排序，时间复杂度为O(n2)，空间复杂度为O(1)，典型的用时间空间。

在链表中实现：挨个取元素，在新的链表中比较并插入

c++11

/**
 * 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) {
        ListNode* res = new ListNode(-1);
        ListNode* cur = res;
        while (head) {
            ListNode* tmp = head->next; //临时存储head的下一个节点
            cur = res; //每次循环前，cur回到队首
            while (cur->next && cur->next->val <= head->val) //下一个节点不为空且值小于等于head,cur前进一位
                cur = cur->next; 
            //否则将head插入cur和cur->next之间
            head->next = cur->next;
            cur->next = head;
            //head指向下一个节点
            head = tmp;
        }
        return res->next;
    }
};

ac结果

Runtime: 52 ms, faster than 58.83% of C++ online submissions for Insertion Sort List.
Memory Usage: 9.6 MB, less than 79.71% of C++ online submissions for Insertion Sort List.