大家好,又见面了,我是你们的朋友全栈君。
题目描述
使用插入排序对链表进行排序。
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
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/164021.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...