LeetCode 147. 對(duì)鏈表進(jìn)行插入排序

題目描述

題目地址：147. 對(duì)鏈表進(jìn)行插入排序
給定單個(gè)鏈表的頭 head ，使用 插入排序 對(duì)鏈表進(jìn)行排序，并返回 排序后鏈表的頭 。

插入排序 算法的步驟:

插入排序是迭代的，每次只移動(dòng)一個(gè)元素，直到所有元素可以形成一個(gè)有序的輸出列表。
每次迭代中，插入排序只從輸入數(shù)據(jù)中移除一個(gè)待排序的元素，找到它在序列中適當(dāng)?shù)奈恢?#xff0c;并將其插入。
重復(fù)直到所有輸入數(shù)據(jù)插入完為止。
下面是插入排序算法的一個(gè)圖形示例。部分排序的列表(黑色)最初只包含列表中的第一個(gè)元素。每次迭代時(shí)，從輸入數(shù)據(jù)中刪除一個(gè)元素(紅色)，并就地插入已排序的列表中。

對(duì)鏈表進(jìn)行插入排序。

解題思路

思路一：使用棧

代碼實(shí)現(xiàn)

c

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/struct ListNode* insertionSortList(struct ListNode* head){if(head==NULL) return head;//設(shè)置虛擬頭結(jié)點(diǎn)struct ListNode* dummyHead=(struct ListNode*)malloc(sizeof(struct ListNode));dummyHead->next=NULL;//dummyHead->next=head;//當(dāng)前節(jié)點(diǎn)（要插入的節(jié)點(diǎn)）curstruct ListNode* cur=head;struct ListNode* pre=dummyHead;//dummyHead->1(pre)->3->4->2(cur)->NULL(next)//如：插入節(jié)點(diǎn)2，操作如下while(cur!=NULL){//循環(huán)中值不小于當(dāng)前值時(shí)候就需要插入當(dāng)前值了while(pre->next!=NULL && pre->next->val<cur->val){pre=pre->next;}//在pre和next之間插入數(shù)據(jù)（2）struct ListNode* next=cur->next;//步驟一：保存cur的下一個(gè)節(jié)點(diǎn)next，因?yàn)楸敬窝h(huán)結(jié)束后，要把當(dāng)前節(jié)點(diǎn)移動(dòng)到下一個(gè)節(jié)點(diǎn)cur->next=pre->next;//步驟二：cur（2）的指針域指向pre->next（3）pre->next=cur;//步驟三：pre（1）的指針域指向cur（2）pre=dummyHead;//步驟四：pre重新指向虛擬頭節(jié)點(diǎn)來(lái)找下一個(gè)插入位置cur=next;//步驟五：cur（2）節(jié)點(diǎn)直接往后移動(dòng)（到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;//設(shè)置虛擬頭結(jié)點(diǎn)ListNode* dummyHead = new ListNode(0);//dummyHead->next=head;//當(dāng)前節(jié)點(diǎn)（要插入的節(jié)點(diǎn)）curListNode* cur=head;ListNode* pre=dummyHead;//dummyHead->1(pre)->3->4->2(cur)->NULL(next)//如：插入節(jié)點(diǎn)2，操作如下while(cur!=NULL){//循環(huán)中值不小于當(dāng)前值時(shí)候就需要插入當(dāng)前值了while(pre->next!=NULL && pre->next->val<cur->val){pre=pre->next;}//在pre和next之間插入數(shù)據(jù)（2）ListNode* next=cur->next;//步驟一：保存cur的下一個(gè)節(jié)點(diǎn)next，因?yàn)楸敬窝h(huán)結(jié)束后，要把當(dāng)前節(jié)點(diǎn)移動(dòng)到下一個(gè)節(jié)點(diǎn)cur->next=pre->next;//步驟二：cur（2）的指針域指向pre->next（3）pre->next=cur;//步驟三：pre（1）的指針域指向cur（2）pre=dummyHead;//步驟四：pre重新指向虛擬頭節(jié)點(diǎn)來(lái)找下一個(gè)插入位置cur=next;//步驟五：cur（2）節(jié)點(diǎn)直接往后移動(dòng)（到next）//dummyHead（pre）->1->2->3->4->NULL}return dummyHead->next;}
};

運(yùn)行結(jié)果

參考文章：

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

思路二：減少遍歷節(jié)點(diǎn)數(shù)

代碼實(shí)現(xiàn)

在這里插入代碼片

運(yùn)行結(jié)果

參考文章：