leetcode5:insertion-sort-list

题目描述

使用插入排序对链表进行排序。

Sort a linked list using insertion sort.

示例1

{3,2,4}

{2,3,4}

// 插入排序就是不断的向一个已经排序的列表中(此处为代码中的sortedList)添加新的节点，并且保证添加节点后的列表仍然有序。

//     一开始的时候sortedList为空，需要遍历输入链表（也就是未排序链表，此处为形参head）的每一个节点，每遍历一个，sortedList加一个。

//      cur代表的就是你当前要加入sortedlist的节点。cur要插入的位置在sortedList的哪里呢？就是此处代码中node的后面。 经过这么一轮，一个节点就被加入到了sortlist。之后同理。 /**

* 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) {

if(head==nullptr || head->next==nullptr) return head;

//在插入时，有可能需要在链表头插入，为了方便，新建立个链表

ListNode sortedList(0);

ListNode *cur=head;

while(cur){

//因为cur的指向可能会改变，所以要预先存下cur的next，以备在下次循环时使用

ListNode *next=cur->next;

//node代表排序数组的当前节点

//从前向后遍历排序数组的每一个节点，和当前未排序数组中的节点做比较

ListNode* node=&sortedList;

while(node->next!=nullptr && node->next->val<cur->val) //以为第一个元素是0，所以从next开始

{

node=node->next;

}

cur->next=node->next;

node->next=cur;

cur=next;

}

return sortedList.next;

}

};