本文共 1578 字，大约阅读时间需要 5 分钟。

题目描述

给定一个链表，请用插入排序的方法，对链表完成排序。

插入排序

插入排序是一种稳定性排序，其主要思想就是把一个元素插入到一个已经排序好的数组中，整个过程就是一个元素找合适的插入位置，有点像打扑克牌的抓牌过程，抓一张牌然后插入到手上一堆牌中的合适位置。

链表的插入排序

链表插入排序的思路和普通数组的方式一样，我们让sortNode始终指向已经完成排序节点的最后一个位置，让insertNode始终指向待插入节点的位置，由于是插入排序，所以每次我们必须从头节点开始遍历，确认insertNode节点应该插入的位置，最后完成插入，并让sortNode和insertNode同时后移一位，继续遍历即可。

代码实现

public ListNode insertSortList(ListNode head) {
           ListNode dummy = new ListNode();        dummy.next = head;        //指向已经完成排序节点的最后一个位置，初始为头节点        ListNode sortNode = head;        //指向待插入节点的位置，初始为第2个节点        ListNode insertNode = head.next;        while (insertNode != null) {
               //如果待插入节点的值大于等于已经排序节点的值，则不用插入            if (insertNode.val >= sortNode.val) {
                   sortNode = sortNode.next;            } else {
                   //从头节点开始遍历，找到insertNode合适的位置                ListNode pre = dummy;                while(pre.next.val <= insertNode.val){
                       pre = pre.next;                }                //找到位置后完成插入                sortNode.next = insertNode.next;                insertNode.next = pre.next;                pre.next = insertNode;            }            insertNode = sortNode.next;        }        return dummy.next;    }

图解过程

初始状态

ListNode pre = dummy;

sortNode.next = insertNode.next;insertNode.next = pre.next;pre.next = insertNode;

insertNode = sortNode.next;

第一次插入完成，重新排列一下。

第二次插入时，insertNode.val >= sortNode.val

所以不用插入，直接把sortNode和insertNode分别向右移动一位

sortNode = sortNode.next;

第三次插入，重复第一次插入的流程

转载地址：http://vhlrb.baihongyu.com/