[LeetCode] Insertion Sort List

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

解题思路
对于得到结点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;

};

LeetCode 75 Sort Colors 颜色分类（荷兰国旗） Given an array with n objects colored red, white or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white and blue. Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.
LeetCode 75. Sort Colors 给定一个具有红色，白色或蓝色的n个对象的数组，对它们进行就地排序，使相同颜色的对象相邻，颜色顺序为红色，白色和蓝色。 这里，我们将使用整数0,1和2分别表示红色，白色和蓝色。 注意：您不应该使用库的排序功能来解决此问题。