C++怎么实现链表插入排序

本篇内容主要讲解“c++怎么实现链表插入排序”，感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷，实用性强。下面就让小编来带大家学习“C++怎么实现链表插入排序”吧!

链表插入排序

链表的插入排序实现原理很简单，就是一个元素一个元素的从原链表中取出来，然后按顺序插入到新链表中，时间复杂度为 O(n2)，是一种效率并不是很高的算法，但是空间复杂度为 O(1)，以高时间复杂度换取了低空间复杂度，参见代码如下：

class Solution {public:    Listnode* insertionSortList(ListNode* head) {        ListNode *dummy = new ListNode(-1), *cur = dummy;        while (head) {            ListNode *t = head->next;            cur = dummy;            while (cur->next && cur->next->val <= head->val) {                cur = cur->next;            }            head->next = cur->next;            cur->next = head;            head = t;        }        return dummy->next;    }};

到此，相信大家对“C++怎么实现链表插入排序”有了更深的了解，不妨来实际操作一番吧！这里是编程网网站，更多相关内容可以进入相关频道进行查询，关注我们，继续学习！