#include<iostream>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
#if 0
class Solution {
public:
ListNode *insertionSortList(ListNode *head) {
ListNode* dummy = new ListNode(0);
ListNode* ppCurrent = dummy;
ListNode* ppNext =ppCurrent->next ;
ppNext = head;
ListNode* pNext = head->next;
if (pNext) {
if (pNext->val < ppNext->val) { //缺少遍历新链表
ppCurrent->next = pNext;
pNext->next = ppNext;
}
else {
ppNext->next = pNext;
}
pNext = pNext->next;
}
}
};
#endif
#if 1
//解释下：
// 插入排序就是不断的向一个已经排序的列表中(此处为代码中的sortedList)添加新的节点，
// 并且保证添加节点后的列表仍然有序。
// 一开始的时候sortedList为空，
// 需要遍历输入链表（也就是未排序链表，此处为形参head）的每一个节点，每遍历一个，sortedList加一个。
// cur代表的就是你当前要加入sortedlist的节点。
// cur要插入的位置在sortedList的哪里呢？就是此处代码中node的后面。
// 经过这么一轮，一个节点就被加入到了sortlist。之后同理。
class Solution {
public:
ListNode *insertionSortList(ListNode *head) {
if (head == nullptr || head->next == nullptr) return head;
//在插入时，有可能需要在链表头插入，为了方便，新建立个链表
ListNode sortedList(0);
ListNode *cur = head;
while (cur) {
//因为cur的指向可能会改变，所以要预先存下cur的next，以备在下次循环时使用
ListNode *next = cur->next;
//node代表排序数组的当前节点
//从前向后遍历排序数组的每一个节点，和当前未排序数组中的节点做比较
ListNode* node = &sortedList;
while (node->next != nullptr && node->next->val<cur->val) //以为第一个元素是0，所以从next开始
{
node = node->next;
}
cur->next = node->next;
node->next = cur;
cur = next;
}
return sortedList.next;
}
};
#endif
https://www.nowcoder.com/questionTerminal/152bc6c5b14149e49bf5d8c46f53152b
