大家好,又见面了,我是你们的朋友全栈君。
使用插入排序对链表进行排序。 Sort a linked list using insertion sort.
输入 {3, 2, 4} 输出 {2, 3, 4}
/** * 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.cn/164021.html原文链接:https://javaforall.cn