链表排序算法

链表排序算法2015-02-15包括冒泡、选择、插入、快排、归并、希尔和堆排序

以下排序算法的正确性都可以在LeetCode的链表排序这一题检测。本文用到的链表结构如下（排序算法都是传入链表头指针作为参数，返回排序后的头指针）

struct ListNode {

int val;

ListNode *next;

ListNode（int x） : val（x）, next（NULL） {}

};

插入排序（算法中是直接交换节点，时间复杂度O（n^2）,空间复杂度O（1））

class Solution {public:ListNode *insertionSortList（ListNode *head） {// IMPORTANT: Please reset any member data you declared, as// the same Solution instance will be reused for each test case.if（head == NULL || head->next == NULL）return head;ListNode *p = head->next, *pstart = new ListNode（0）, *pend = head;pstart->next = head; //为了操作方便，添加一个头结点while（p ！= NULL）{ListNode *tmp = pstart->next, *pre = pstart;while（tmp ！= p && p->val >= tmp->val） //找到插入位置{tmp = tmp->next; pre = pre->next;}if（tmp == p）pend = p;else{pend->next = p->next;p->next = tmp;pre->next = p;}p = pend->next;}head = pstart->next;delete pstart;return head;}};

选择排序（算法中只是交换节点的val值，时间复杂度O（n^2）,空间复杂度O（1））

class Solution {public:ListNode *selectSortList（ListNode *head） {// IMPORTANT: Please reset any member data you declared, as// the same Solution instance will be reused for each test case.//选择排序if（head == NULL || head->next == NULL）return head;ListNode *pstart = new ListNode（0）;pstart->next = head; //为了操作方便，添加一个头结点ListNode*sortedTail = pstart;//指向已排好序的部分的尾部while（sortedTail->next ！= NULL）{ListNode*minNode = sortedTail->next, *p = sortedTail->next->next;//寻找未排序部分的最小节点while（p ！= NULL）{if（p->val < minNode->val）minNode = p;p = p->next;}swap（minNode->val, sortedTail->next->val）;sortedTail = sortedTail->next;}head = pstart->next;delete pstart;return head;}};