# [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 *temp;
while(current != NULL)
{
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;
}
}
};

{
while(tmp)
{
cout<<tmp->val<<" ";
tmp = tmp->next;
}
cout<<endl;
}

int main()
{
ListNode* node1 = new ListNode(8);
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;

Solution s;
}

/*****************************************************************
*  @Author   : 楚兴
*  @Date     : 2015/2/16 14:44
*  @Status   : Accepted
*  @Runtime  : 96 ms
******************************************************************/
class Solution {
public:
{
}

ListNode *temp;
ListNode *newcur;

while(cur != NULL)
{
newcur = cur->next;
if (temp == head && temp->val > cur->val)  //头结点的值大于当前结点的值
{
pre->next = pre->next->next;
cur->next = temp;
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;
}

}
};

|
7月前
|
Java
Leetcode 114. Flatten Binary Tree to Linked List

22 1
|
7月前
|
C++
Leetcode Copy List with Random Pointer（面试题推荐）

30 0
|
7月前
Leetcode 19.Remove Nth Node From End of List

23 0
|
1月前
|
C++ 容器
【C++】STL容器——探究List与Vector在使用sort函数排序的区别（14）
【C++】STL容器——探究List与Vector在使用sort函数排序的区别（14）
38 0
|
1月前
|

「LeetCode合集」链表（List）及经典问题
「LeetCode合集」链表（List）及经典问题
32 0
|
11月前
|

SGI-STL源码剖析之list::sort()
SGI-STL源码剖析之list::sort()
81 0
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.
72 0
|

LeetCode 141. 环形链表 Linked List Cycle
LeetCode 141. 环形链表 Linked List Cycle
87 0
|
5天前
|

【6月更文挑战第11天】🏆本文收录于「滚雪球学Java」专栏，专业攻坚指数级提升，希望能够助你一臂之力，帮你早日登顶实现财富自由🚀；同时，欢迎大家关注&&收藏&&订阅！持续更新中，up！up！up！！
21 2
|
6天前
|

Java集合详解：Set, Map, Vector, List的对比与联系