leetcode, LC5: insertion-sort-list

题目描述

使用插入排序对链表进行排序。
Sort a linked list using insertion sort.

示例1

输入

{3, 2, 4}

输出

{2, 3, 4}

解题思路

1. new 一个新的 ListNode 作为选择排序好的链表的表头
2. 对于原始链表中的每一个结点
   2.1. 寻找新链表中该结点的插入位置
   2.2 插入该结点
3. 返回新链表

代码实现

/*** struct ListNode {*	int val;*	struct ListNode *next;* };*/class Solution {
public:/*** * @param head ListNode类 * @return ListNode类*/ListNode* insertionSortList(ListNode* head) {// write code hereif(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