147. Insertion Sort List

发表于 | 分类于

每日一题 2019 - 05 - 11

题目：

Sort a linked list using insertion sort.

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

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

解法：

这个题让使用插入排序对一个链表进行排序，解法非常简单，就是拿出一个结点，连接在另外一个结点上，但是在代码实践上会有许多问题，比如原结点的提取，新插入位置的确定以及新结点的插入，要注意指针的非空性以及指针的遍历过程；

代码：

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
/**
 * 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* dummyHead = new ListNode(0);
        ListNode* pre = dummyHead;;  //插入位置的前一个节点
        ListNode* cur = head;;  //待排序的节点
        ListNode* rear; //待排序节点的下一个节点
        while(cur != NULL){
            rear = cur->next;
            while(pre->next != NULL && pre->next->val < cur->val){
                pre = pre->next;
            }
            cur->next = pre->next;
            pre->next = cur;
            cur = rear;
            pre = dummyHead;
        }
        return dummyHead->next;
    }
};
0%
undefined