[LeetCode] Insertion Sort List

Sort a linked list using insertion sort.

解题思路 对于得到结点current的插入位置，从头结点开始遍历，直到遍历到值大于等于节点current的结点，，然后将从该结点到current的前驱结点的所有结点的值依次和current结点的值交换，从而达到将该节点插入所遍历到的位置的目的。

实现代码

/****************************************************************** @Author : 楚兴* @Date: 2015/2/16 00:06* @Status : Accepted* @Runtime : 287 ms******************************************************************/#include <iostream>using namespace std;struct ListNode {int val;ListNode *next;ListNode(int x) : val(x), next(NULL) {}};class Solution {public:ListNode *insertionSortList(ListNode *head) {head->next == NULL){return head;}ListNode *current = head->next;ListNode *temp;while(current != NULL){temp = head;while(temp != current && temp->val < current->val){temp = temp->next;}if (temp != current){while (temp != current){swap(temp->val, current->val);temp = temp->next;}}current = current->next;}return head;}};void print(ListNode *head){ListNode *tmp = head;while(tmp){cout<<tmp->val<<” “;tmp = tmp->next;}cout<<endl;}int main(){ListNode* head = new ListNode(12);ListNode* node1 = new ListNode(8);head->next = node1;ListNode* node2 = new ListNode(5);node1->next = node2;ListNode* node3 = new ListNode(9);node2->next = node3;ListNode* node4 = new ListNode(0);node3->next = node4;ListNode* node5 = new ListNode(1);node4->next = node5;ListNode* node6 = new ListNode(3);node5->next = node6;ListNode* node7= new ListNode(6);node6->next = node7;ListNode* node8 = new ListNode(4);node7->next = node8;print(head);Solution s;s.insertionSortList(head);print(head);}

上述代码虽然已经被AC，但是用时还是太久，感觉主要是因为交换的次数太多了。故将代码更改如下：

/****************************************************************** @Author : 楚兴* @Date: 2015/2/16 14:44* @Status : Accepted* @Runtime : 96 ms******************************************************************/class Solution {public:ListNode *insertionSortList(ListNode *head) {head->next == NULL){return head;}ListNode *cur = head->next; //当前结点ListNode *pre = head; //当前结点的前驱结点ListNode *temp;ListNode *newcur;while(cur != NULL){temp = head;newcur = cur->next;if (temp == head && temp->val > cur->val) //头结点的值大于当前结点的值{pre->next = pre->next->next;cur->next = temp;head = cur;cur = newcur;continue;}//找到其后继结点的值不大于不大于当前结点值的temp结点while (temp->next != cur && temp->next->val < cur->val){temp = temp->next;}if (temp->next != cur){pre->next = pre->next->next;ListNode *t = temp->next;temp->next = cur;cur->next = t;}else{//位于当前结点之前的所有结点的值均小于当前结点pre = pre->next;}cur = newcur;}return head;}};

比天才难得，许多天赋差的人经过过勤学苦练也取得了很大的成功。