[LeetCode] Insertion Sort List

本文主要是介绍[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) {if (head == NULL || 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) {if (head == NULL || 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;}
};