力扣———對鏈表的插入排序（畫圖詳解）-有解無憂

題目：
在這里插入圖片描述

對鏈表進行插入排序
插入排序的影片演示如上，從第一個元素開始，該鏈表可以被認為已經部分排序，
每次迭代時，從輸入資料中移除一個元素，并原地將其插入到已排好序的鏈表中，（轉載力扣）

插入排序演算法：
插入排序是迭代的，每次只移動一個元素，直到所有元素可以形成一個有序的輸出串列，
每次迭代中，插入排序只從輸入資料中移除一個待排序的元素，找到它在序列中適當的位置，并將其插入，
重復直到所有輸入資料插入完為止，

示例1：

輸入: 4->2->1->3
輸出: 1->2->3->4

示例2

輸入: -1->5->3->4->0
輸出: -1->0->3->4->5

分析
在這里插入圖片描述

先把鏈表分成兩個部分:把第一個數，與后面的數分開，然后在把后面的數一個一個與前面進行進行對比，在插入進去

首先我們需要先對第二個鏈表定義兩個指標:cur，next（cur是指向的值是跟前面的鏈表進行對比），next是cur的下一個值
對第一個鏈表定義兩個指標，head，c,p,head是第一個鏈表的頭節點，c是要跟第二個鏈表進行比較的當前的值，p是c前一個值，

頭插，也就是p為null時,cur<c,插入完之后在把cur賦值給head
在這里插入圖片描述

插在中間，p不等于null卻cur<c
在這里插入圖片描述

c回圈結束后，進行尾插：

6,color_FFFFFF,t_70)

struct ListNode* insertionSortList(struct ListNode* head){
    //先判斷head是否為NULL
    if(head==NULL||head->next==NULL)
    {
        return head;
    }
    //先定義cur
   struct   ListNode* cur=head->next;
    head->next=NULL;//將兩個鏈表斷開
    while(cur)//當cur為空時，則回圈結束
    {
         struct ListNode* c=head;//定義第一鏈表的c,和p
      struct  ListNode* p=NULL;
      struct  ListNode*  next=cur->next;//定義第二個鏈表的下一個節點
        while(c)//第二個回圈
        {
            if(cur->val<c->val)//當找到cur比c小，跳出來
            {
                break;
            }
            else//找不到繼續找
            {
                p=c;
                c=c->next;
            }
        }
        if(p==NULL)//一種是插在最前面
        {
            cur->next=c;
            head=cur;
        }
        else//另外一種是尾插，或者插在中間
        {
            p->next=cur;
            cur->next=c;
        }
        cur=next;//最后cur在走一步

    }
    return head;
}

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/278174.html

標籤：其他

上一篇：Final Cut Pro for Mac(fcpx蘋果視頻剪輯軟體)V10.5.2中文版介紹

下一篇：歐拉函式及模板