leetcode——对链表进行插入排序

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了leetcode——对链表进行插入排序，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1226字，纯文字阅读大概需要2分钟。

内容图文

思路：
1.如果链表为空，则返回其本身；
2.如果链表不为空，初始化排序表最后指针lastsorted为head，当前需排序的指针curr为head->next；
3.为了方便将元素插入到head之前，设立Head_front指针，值设为0，指向head；
4.初始化完成后，对排好序的表利用指针prev进行遍历查找，找到适合插入的位置；

				ListNode *prev = Head_front;
                while (prev->next->val <= curr->val)
                    prev = prev->next;

5.将需排序元素curr原地删除，插入新的位置中；

 				lastSorted->next = curr->next;
                curr->next = prev->next;
                prev->next = curr;

6.循环4和5步骤，直到curr为nullptr，最后需要返回链表头元素，return Head_front->next;

代码：

class Solution {
public:
    ListNode* insertionSortList(ListNode* head) {
        if (head == nullptr) 
            return head;
        
        ListNode* Head_front = new ListNode(0,head);
        ListNode* lastSorted = head;
        ListNode* curr = head->next;
        while (curr != nullptr) {
            //当前值大于排好序的表的最后一个值
            if (lastSorted->val <= curr->val) 
                lastSorted = lastSorted->next;
            //当前值在排好序表中排列在之前或中间
            else {
                ListNode *prev = Head_front;
                //寻找最佳插入位置
                while (prev->next->val <= curr->val)
                    prev = prev->next;
                //删除和插入操作
                lastSorted->next = curr->next;
                curr->next = prev->next;
                prev->next = curr;
            }
            //进行下一个元素的排序
            curr = lastSorted->next;
        }
        return Head_front->next;
    }
};

时间复杂度	空间复杂度
O（n2）	O(1)

内容总结

以上是互联网集市为您收集整理的leetcode——对链表进行插入排序全部内容，希望文章能够帮你解决leetcode——对链表进行插入排序所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---