【leetcode】147 Insertion Sort List总结

插入排序

题意

使用插入排序对一个单链表进行排序

思路

说实话，没思路。先看看数组的插入排序吧，也许能找到灵感：

数组插入排序

数组的插入排序，需要对数组进行两重遍历，第一次找到一个比前面数字小的一个数字，说明它需要被移动到前面去，所以再从当前节点开始从后往前遍历，将每一个比其大的数字都往后移一位，直到找到一个比它小的数字，然后插入在这个数字后面，代码如下：

public static void insertSort(int[] array) { 
    int len = array.length; 
    if(len <= 1) 
        return; 
    //从第二位开始遍历，找到前一位比后一位大的数字，说明该数字需要被插入到前面去 
    for(int i=1;i<len;i++) { 
        if(array[i-1] > array[i]) { 
        		//临时变量保存array[i] 
            int temp = array[i]; 
            int j=i; 
            //从后往前把所有比temp大的数往后移一位 
            while (j>0 && array[j-1] > temp) { 
                array[j] = array[j-1]; 
                j--; 
            } 
            //把temp放在比temp小的数的后面 
            array[j] = temp; 
        } 
    } 
    for(int i : array) 
        System.out.printf("%d\t", i); 
} 

链表插入排序

到了链表，我们发现一个问题，那就是链表不能从后往前遍历，这就很尴尬了。我本来是尝试找到一个需要移动的节点（即该节点的值比前驱节点的值小），从前往后遍历，直到找到一个节点值比它大时插入到这个节点前面，然而实现了很久发现代码又臭又长，关键是还总有测试用例不通过，最后还是放弃了。

看了答案发现思路应该是创建一个辅助的新链表，并且使用一个指针遍历原链表，每次将原链表中的一个节点插入到新链表的合适位置（即该节点的值大于新链表上的节点的值，又小于后一节点的值）。最后将新链表的头部返回即可。代码如下，做了详细的注释，应该很容易看懂。

class ListNode { 
    int val; 
    ListNode next; 
    ListNode(int x) { 
        val = x; 
    } 
} 
/** 
 * 链表插入排序 
 * */ 
public ListNode insertionSortList(ListNode head) { 
	//边界条件判断 
    if(head==null || head.next == null) 
        return head; 
 
    //创造一个新的链表头部 
    ListNode pre = new ListNode(-1); 
    //用一个临时变量保存头节点 
    ListNode ans = pre; 
    //cur是原链表上的指针 
    ListNode cur = head; 
    while (cur != null) { 
        //每次循环前重置pre为头结点，这样保证每次都从头往后遍历 
        pre = ans; 
         
        //当pre.next.val大于cur.val时停止循环 
        while (pre.next != null && pre.next.val < cur.val) { 
            pre = pre.next; 
        } 
 
        //pre.next.val 大于 cur.val，此时应该把cur插入到pre后 
        //保存原链表当前节点的下一节点 
        ListNode tmp = cur.next; 
        //把cur插入到pre之后 
        cur.next = pre.next; 
        pre.next = cur; 
         
        //cur指针后移一位 
        cur = tmp; 
    } 
    return ans.next; 
} 

总结

发现自己做题总是一根筋，直肠子，不知道拐弯，实际上很多题目都不是用常规思维去解的，比如这题就需要一个辅助链表来完成，希望多锻炼能知道更多的套路吧。