大家好，又见面了，我是全栈君。
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 ，如需转载请自行联系原博主。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/107859.html原文链接：https://javaforall.net
