大家好,又见面了,我是全栈君。
Sort a linked list using insertion sort.
链表的插入排序实现原理很简单,就是一个元素一个元素的从原链表中取出来,然后按顺序插入到新链表中,时间复杂度为O(n2),是一种效率并不是很高的算法,但是空间复杂度为O(1),以高时间复杂度换取了低空间复杂度。代码如下:
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode *insertionSortList(ListNode *head) { ListNode *res = new ListNode(-1); ListNode *cur = res; while (head) { ListNode *next = head->next; cur = res; while (cur->next && cur->next->val <= head->val) { cur = cur->next; } head->next = cur->next; cur->next = head; head = next; } return res->next; } };
本文转自博客园Grandyang的博客,原文链接:链表插入排序[LeetCode] Insertion Sort List ,如需转载请自行联系原博主。
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/107859.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...