【leetcode】147 Insertion Sort List总结

熊孩纸 阅读:356 2022-03-12 16:24:52 评论:0
本文章主要介绍了【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; 
} 

总结

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


标签:加密算法
声明

1.本站遵循行业规范,任何转载的稿件都会明确标注作者和来源;2.本站的原创文章,请转载时务必注明文章作者和来源,不尊重原创的行为我们将追究责任;3.作者投稿可能会经我们编辑修改或补充。

我的关注

全民解析

搜索
排行榜
关注我们