力扣（LeetCode） -147 对链表进行插入排序

本题考察的插入排序和链表操作

题目描述

对链表进行插入排序。

插入排序算法：
插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
重复直到所有输入数据插入完为止。

示例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;
        }
    }
}