Insertion Sort List（C++对链表进行插入排序）

刺骨的言语ヽ痛彻心扉 2023-01-17 08:59 81阅读 0赞

（1）插入排序

/**
     * 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==nullptr || head->next==nullptr) return head;
            ListNode *new_head=new ListNode(0);
            new_head->next=head;
            ListNode *LastSort=head,*cur=head->next,*prev=new_head;
            
            while(cur!=nullptr) {
                if(cur->val>=LastSort->val) {
                    LastSort=LastSort->next;
                    cur=cur->next;
                } else {
                    prev=new_head;
                    while(prev->next->val<cur->val) {
                        prev=prev->next;
                    }
                    LastSort->next=cur->next;
                    cur->next=prev->next;
                    prev->next=cur;
                    
                    cur=LastSort->next;
                }
            }
            return new_head->next;
        }
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，81人围观）

还没有评论，来说两句吧...

相关阅读

相关 147. 对链表进行插入排序

题目描述 [147. 对链表进行插入排序][147.] 题目来源 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_

痛定思痛。/ 2023年02月20日 13:39/ 0 赞/ 17 阅读

相关 Insertion Sort List（C++对链表进行插入排序）

（1）插入排序 / Definition for singly-linked list. struct ListNode {

刺骨的言语ヽ痛彻心扉/ 2023年01月17日 08:59/ 0 赞/ 82 阅读

相关 166-对链表进行插入排序

题目如下：对一条链表进行排序算法，要求使用算法为插入排序，且时间复杂度符合O(n^2) 解题方法： 1、判断链表是否为空，为空直接返回 2、新建排序链表头和尾都

电玩女神/ 2022年10月26日 12:52/ 0 赞/ 181 阅读

相关 leetcode 147. Insertion Sort List 链表插入排序

Sort a linked list using insertion sort. 本题就是要做链表的插入排序。代码如下： /class ListNode

矫情吗；*/ 2022年06月08日 04:58/ 0 赞/ 202 阅读

相关 [Leetcode][python]Insertion Sort List/对链表进行插入排序

题目大意通过插入排序的方法排序一个链表。解题思路参考：[http://www.cnblogs.com/zuoyuan/p/3700105.html][htt

古城微笑少年丶/ 2022年06月03日 03:00/ 0 赞/ 204 阅读

相关插入排序（Insertion Sort）

一，插入排序算法分析插入排序算法有种递归的思想在里面，它由N-1趟排序组成。初始时，只考虑数组下标0处的元素，只有一个元素，显然是有序的。然后第一趟对下标 1 处的元

谁践踏了优雅/ 2022年05月26日 09:42/ 0 赞/ 136 阅读

相关 5. insertion-sort-list 链表插入排序

题目描述 Sort a linked list using insertion sort. 对一个链表进行插入排序题目解析上一道题对链表进行归并排序和冒泡排

阳光穿透心脏的1/2处/ 2022年05月23日 11:24/ 0 赞/ 154 阅读

相关对一个链表进行插入排序

![这里写图片描述][70] class ListNode { int val; ListNode next;

灰太狼/ 2022年05月23日 02:50/ 0 赞/ 203 阅读

相关 LeetCode 147.Insertion Sort List (对链表进行插入排序)

题目描述：对链表进行插入排序。 ![Insertion-sort-example-300px.gif][] 插入排序的动画演示如上。从第一个元素开始，该链表可以被认为

川长思鸟来/ 2022年05月08日 13:33/ 0 赞/ 204 阅读

相关插入排序 Insert sort

//直接插入排序 void DirectInsertionSort(int arr, int nLen) { int i, j;

港控/mmm°/ 2021年12月20日 15:03/ 0 赞/ 284 阅读