Sort a linked list using insertion sort.
仍然是一个很简洁的题目，让我们用插入排序给链表排序；这里说到插入排序。能够来回想一下， 最主要的入门排序算法。就是插入排序了。时间复杂度为n^2。最主要的插入排序是基于数组实现的。以下给出基于数组实现的插入排序，来体会一个插入排序的思想；
下面仅为数组实现。不是解题代码，没兴趣能够跳过。
void insertionsort (int a[], int N)
{
for (int i = 1; i < N; i++){
int tmp = a[i];
for (int j = i; j >= 0 && a[j] < a[j - 1]; j--) //这里是升序排列，所以是a[j] < a[j - 1]
a[j] = a[j - 1];
a[j] = tmp;
}
}
当做链表的时候，有两点主要差别：一、因为是单向链表。所以和数组不同的是，每一次都从第一个节点向后扫描。寻找合适的插入位置；当然。数组也是能够这种。
二、数组须要挨个替换。我上面的写法在寻找合适位置的同一时候就直接替换了，所以感觉没那么明显，而链表则是在需找到合适位置之后，把待排序节点拿出插入当中。体现了链表的动态性。
/**
* 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) {
if (head == NULL || head->next == NULL)
return head; ListNode *tmp = NULL;
ListNode *pre_tmp = NULL;
ListNode *dummy = new ListNode(0);
ListNode *pos = head->next; //这里用pos指向第一待插入排序数据
ListNode *pre_pos = head;
dummy->next = head; while(pos != NULL){
tmp = dummy->next; //这里一開始写成了 tmp = head 一直错，太不细心了。在引入哑节点之后，
//这里就不能等于head,仅仅有这样才干够从第一个開始扫描開始扫描。
pre_tmp = dummy;
while(tmp->val < pos->val && tmp != pos){ //第二个条件在数组插入排序时事不用推断的。这里须要注意！
pre_tmp = tmp;
tmp = tmp->next;
} if (tmp != pos)
{
pre_pos->next = pos->next;
pre_tmp->next = pos;
pos->next = tmp;
pos = pre_pos;
}
pre_pos = pos;
pos = pos->next;
}
return dummy->next;
}
};
PS：dummy节点对于头节点可能变化的链表来说，引入是一个非常方便的事情，可是要记得链表的起始用dummy->next表示出，而不是使用head，由于head由于改变节点点，它可能不是头节点 orz
版权声明：本文博主原创文章，博客，未经同意不得转载。