本题考察的插入排序和链表操作
题目描述
对链表进行插入排序。
插入排序算法：
插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
重复直到所有输入数据插入完为止。
示例1:
输入: 4->2->1->3
输出: 1->2->3->4
示例2:
输入: -1->5->3->4->0
输出: -1->0->3->4->5
题目思考
思路很直观，遍历链表中的每一个结点，通过逐个比较将每个结点插入到正确的位置。注意结点处于开头和结尾等特殊情况。
代码
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
ListNode myHead;
public ListNode insertionSortList(ListNode head) {
ListNode cursor=head;
myHead=head;
while(cursor!=null){
ListNode temp=cursor.next;
if(temp!=null&&temp.val<cursor.val){ //如果该结点的后一个结点比该节点小
cutLink(cursor); //将后一个结点从链表中取出
insertNode(temp,head); //将后一个结点插入到适合的位置
}else{
cursor=cursor.next;
}
}
return myHead;
}
public void cutLink(ListNode one){
ListNode two=one.next;
ListNode three=two.next;
one.next=three;
two.next=null;
}
public void insertNode(ListNode node,ListNode head){
ListNode temp=myHead;
ListNode pre=null;
while(node.val>temp.val){
pre=temp;
temp=temp.next;
}
node.next=temp;
if(pre!=null){
pre.next=node;
}else{
myHead=node;
}
}
}
看了一下别人提交的代码，发现100%的那个代码竟然是用归并排序做的。虽然与题目要求的插入排序不符，但是代码思路挺好的，值得学习一下。下面是归并排序的代码。归并排序的思想先将数据拆分，一直拆分到最小单元。然后将最小单元两两合并，并且排序，得到稍大的有序单元，不断对数据合并，直到将所有数据合并成一个有序序列。示意图如下图所示
image.png
代码如下所示
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode insertionSortList(ListNode head) {
if(head==null||head.next==null)
return head;
ListNode fast=head,slow=head,pre=null;
while(fast!=null&&fast.next!=null){ //将链表二等分
pre=slow;
slow=slow.next;
fast=fast.next.next;
}
pre.next=null; //将链表从中间截断
ListNode left=insertionSortList(head); //递归，继续截断链表，直到不可截断
ListNode right=insertionSortList(slow); //递归，继续截断链表，直到不可截断
return merge(left,right); //对得到的两个短链表进行排序
}
public ListNode merge(ListNode left,ListNode right){
if(left==null)
return right;
if(right==null)
return left;
if(left.val<right.val){
left.next=merge(left.next,right);
return left;
}else{
right.next=merge(left,right.next);
return right;
}
}
}
