C++实现LeetCode(147.链表插入排序)

这篇文章主要介绍了C++实现LeetCode(147.链表插入排序),本篇文章通过简要的案例,讲解了该项技术的了解与使用,以下就是详细内容,需要的朋友可以参考下

C++实现LeetCode(147.链表插入排序),久久派带你了解更多相关信息。

[LeetCode] 147. Insertion Sort List 链表插入排序

Sort a linked list using insertion sort.
A graphical example of insertion sort. The partial sorted list (black) initially contains only the first element in the list.
With each iteration one element (red) is removed from the input data and inserted in-place into the sorted list

Algorithm of Insertion Sort:

  1. Insertion sort iterates, consuming one input element each repetition, and growing a sorted output list.
  2. At each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there.
  3. It repeats until no input elements remain.

Example 1:

Input: 4->2->1->3
Output: 1->2->3->4

Example 2:

Input: -1->5->3->4->0
Output: -1->0->3->4->5

链表的插入排序实现原理很简单,就是一个元素一个元素的从原链表中取出来,然后按顺序插入到新链表中,时间复杂度为 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;    }};

Github 同步地址:

https://github.com/grandyang/leetcode/issues/147

类似题目:

Sort List

Insert into a Cyclic Sorted List

参考资料:

https://leetcode.com/problems/insertion-sort-list/

https://leetcode.com/problems/insertion-sort-list/discuss/46423/Explained-C%2B%2B-solution-(24ms)

https://leetcode.com/problems/insertion-sort-list/discuss/46420/An-easy-and-clear-way-to-sort-(-O(1)-space-)

到此这篇关于C++实现LeetCode(147.链表插入排序)的文章就介绍到这了,更多相关C++实现链表插入排序内容请搜索趣讯吧以前的文章或继续浏览下面的相关文章希望大家以后多多支持趣讯吧!

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,请发送邮件至 203304862@qq.com 举报,一经查实,本站将立刻删除。转转请注明出处:https://www.szhjjp.com/n/7881.html

发表评论

登录后才能评论