大家好，又见面了，我是你们的朋友全栈君。
题目描述
使用插入排序对链表进行排序。
Sort a linked list using insertion sort.
示例1
输入
{3, 2, 4}
输出
{2, 3, 4}
解题思路
- new 一个新的 ListNode 作为选择排序好的链表的表头
- 对于原始链表中的每一个结点
2.1. 寻找新链表中该结点的插入位置
2.2 插入该结点 - 返回新链表
代码实现
/** * struct ListNode { * int val; * struct ListNode *next; * }; */
class Solution {
public:
/** * * @param head ListNode类 * @return ListNode类 */
ListNode* insertionSortList(ListNode* head) {
// write code here
if(head == NULL || head->next == NULL) return head;
ListNode* currNode;
ListNode* retLListHead = new ListNode(0);
ListNode* retLListCurrNodeLast;
ListNode* retLListCurrNode;
while(head){
currNode = head;
retLListCurrNodeLast = retLListHead;
retLListCurrNode = retLListCurrNodeLast->next;
head = head->next;
while(retLListCurrNode && retLListCurrNode->val < currNode->val){
retLListCurrNodeLast = retLListCurrNodeLast->next;
retLListCurrNode = retLListCurrNode->next;
}
currNode->next = retLListCurrNode;
retLListCurrNodeLast->next = currNode;
}
return retLListHead->next;
}
};
运行结果
运行时间：27ms
占用内存：632k
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/164021.html原文链接：https://javaforall.net
