首页 > 代码库 > [Leetcode] insertion sort list 链表插入排序

[Leetcode] insertion sort list 链表插入排序

Sort a linked list using insertion sort.

 题意:使用插入排序排链表。

思路:所谓的插入排序法,可以理解为,从原链表中取结点,每次都从新的链表的开头开始遍历比较,在新链表中找到不小于当前节点的位置,然后将当前节点插入进去,依次重复这种过程,时间复杂度为O(n^2)。比较大小时可以采用以结点后缀的形式去比较,这样可以在已排好序的新链表中找到最后一个小于当前值的位置,可以省略一多定义一个指针,这种写法还是很值得思考的。还有就是连接新链表时,先连好后面的,然后再连接前面的。还有值得注意的是,每次比较都是从新链表的开始比较,所以要先定位好最开始的起始点。代码如下:

 1 /**
 2  * Definition for singly-linked list.
 3  * struct ListNode {
 4  *     int val;
 5  *     ListNode *next;
 6  *     ListNode(int x) : val(x), next(NULL) {}
 7  * };
 8  */
 9 class Solution {
10 public:
11     ListNode *insertionSortList(ListNode *head) 
12     {
13         ListNode *newList=new ListNode(-1);
14         while(head)
15         {
16             ListNode *temp=head->next;
17             ListNode *cur=newList;
18             while(cur->next&&cur->next->val<head->val)
19                 cur=cur->next;
20 
21             head->next=cur->next;
22             cur->next=head;
23             head=temp;
24             
25         }   
26         return newList->next;
27     }
28 };

 

[Leetcode] insertion sort list 链表插入排序