LeetCode 147. 对链表进行插入排序

题目描述

题目地址：147. 对链表进行插入排序
给定单个链表的头 head ，使用 插入排序 对链表进行排序，并返回 排序后链表的头 。

插入排序 算法的步骤:

插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
重复直到所有输入数据插入完为止。
下面是插入排序算法的一个图形示例。部分排序的列表(黑色)最初只包含列表中的第一个元素。每次迭代时，从输入数据中删除一个元素(红色)，并就地插入已排序的列表中。

对链表进行插入排序。

解题思路

思路一：使用栈

代码实现

c

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/struct ListNode* insertionSortList(struct ListNode* head){if(head==NULL) return head;//设置虚拟头结点struct ListNode* dummyHead=(struct ListNode*)malloc(sizeof(struct ListNode));dummyHead->next=NULL;//dummyHead->next=head;//当前节点（要插入的节点）curstruct ListNode* cur=head;struct ListNode* pre=dummyHead;//dummyHead->1(pre)->3->4->2(cur)->NULL(next)//如：插入节点2，操作如下while(cur!=NULL){//循环中值不小于当前值时候就需要插入当前值了while(pre->next!=NULL && pre->next->val<cur->val){pre=pre->next;}//在pre和next之间插入数据（2）struct ListNode* next=cur->next;//步骤一：保存cur的下一个节点next，因为本次循环结束后，要把当前节点移动到下一个节点cur->next=pre->next;//步骤二：cur（2）的指针域指向pre->next（3）pre->next=cur;//步骤三：pre（1）的指针域指向cur（2）pre=dummyHead;//步骤四：pre重新指向虚拟头节点来找下一个插入位置cur=next;//步骤五：cur（2）节点直接往后移动（到next）//dummyHead（pre）->1->2->3->4->NULL}return dummyHead->next;
}

C++

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* insertionSortList(ListNode* head) {if(head==NULL) return head;//设置虚拟头结点ListNode* dummyHead = new ListNode(0);//dummyHead->next=head;//当前节点（要插入的节点）curListNode* cur=head;ListNode* pre=dummyHead;//dummyHead->1(pre)->3->4->2(cur)->NULL(next)//如：插入节点2，操作如下while(cur!=NULL){//循环中值不小于当前值时候就需要插入当前值了while(pre->next!=NULL && pre->next->val<cur->val){pre=pre->next;}//在pre和next之间插入数据（2）ListNode* next=cur->next;//步骤一：保存cur的下一个节点next，因为本次循环结束后，要把当前节点移动到下一个节点cur->next=pre->next;//步骤二：cur（2）的指针域指向pre->next（3）pre->next=cur;//步骤三：pre（1）的指针域指向cur（2）pre=dummyHead;//步骤四：pre重新指向虚拟头节点来找下一个插入位置cur=next;//步骤五：cur（2）节点直接往后移动（到next）//dummyHead（pre）->1->2->3->4->NULL}return dummyHead->next;}
};

运行结果

参考文章：

https://leetcode.cn/problems/insertion-sort-list/solutions/491331/147-kao-cha-lian-biao-zong-he-cao-zuo-xiang-jie-by/?q=%E4%BB%A3%E7%A0%81&orderBy=most_relevant

思路二：减少遍历节点数

代码实现

在这里插入代码片

运行结果

参考文章：