/**
* Definition for singly-linked list.
*/ struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(nullptr) {}
};
class Solution {
public:
ListNode *insertionSortList(ListNode *head) {
if (head == nullptr || head->next == nullptr)
return head;
ListNode * pstart = new ListNode(0);
//创建一个辅助节点，有利于插入这个节点是头结点
pstart->next = head;
//设置一个比较节点
ListNode *p = head->next;
//定义一个节点用来指向每次要插入的节点
ListNode *pend = head;
while (p != nullptr)
{
ListNode * pre = pstart;
//因为每次都是从第一个节点开始比较
ListNode *temp = pstart->next;
while (p != temp && p->val >= temp->val) //节点只能和该节点之前的节点进行比较
{
temp = temp->next;
pre = pre->next;
//这个过程是找到比插入节点大的节点，插入到这个节点前面
}
if (p == temp) //如果插入的节点之前的节点都比该节点的值小，那么就进行下一个节点
pend = temp;
else{
/*
如果找到比这个节点大的节点，进行插入
*/
pend->next = p->next;
p->next = temp;
pre->next = p;
}
p = pend->next;
//pend节点要一直指向当前插入的节点 }
head = pstart->next;
delete pstart;
return head;
}
};
推荐阅读
- 数据结构与算法|【算法】力扣第 266场周赛
- leetcode|今天开始记录自己的力扣之路
- Python|Python 每日一练 二分查找 搜索旋转排序数组 详解
- 【LeetCode】28.实现strstr（） （KMP超详细讲解，sunday解法等五种方法，java实现）
- LeetCode-35-搜索插入位置-C语言
- leetcode python28.实现strStr()35. 搜索插入位置
- Leetcode Permutation I & II
- python|leetcode Longest Substring with At Most Two Distinct Characters 滑动窗口法
- LeetCode 28 Implement strStr() (C,C++,Java,Python)
- Python|Python Leetcode(665.非递减数列)