[Leetcode][python]Insertion Sort List/对链表进行插入排序

古城微笑少年丶 2022-06-03 03:00 193阅读 0赞

## 题目大意 ##

通过插入排序的方法排序一个链表。

## 解题思路 ##

参考：[http://www.cnblogs.com/zuoyuan/p/3700105.html][http_www.cnblogs.com_zuoyuan_p_3700105.html]

![这里写图片描述][70]

1.  用current往后找，找到比之前小的数。
2.  每次都用pre从dummy开始，找到该插入的位置，插入。

## 代码 ##

class Solution(object):
        def insertionSortList(self, head):
            """
            :type head: ListNode
            :rtype: ListNode
            """
            if not head:
                return head
            dummy = ListNode(0)
            dummy.next = head
            curr = head
            while curr.next:
                if curr.next.val < curr.val:  # 直到某数小于其前面的数，进入
                    pre = dummy  # 回到头开始往后遍历                        
                    while pre.next.val < curr.next.val:  # 用pre直到找到应该插入的位置
                        pre = pre.next
                    # 如上图
                    tmp = curr.next  # 把2保存到temo               
                    curr.next = tmp.next # 把4指向2的后面一位
                    tmp.next = pre.next  # 2指向3
                    pre.next = tmp  # 1指向2
                else:
                    curr = curr.next
            return dummy.next

## 总结 ##

[http_www.cnblogs.com_zuoyuan_p_3700105.html]: http://www.cnblogs.com/zuoyuan/p/3700105.html
[70]: /images/20220603/5ac79ba8c1fd4a9c8ff6039aaee3ef22.png

发表评论取消回复

表情：

评论列表（有 0 条评论，193人围观）

还没有评论，来说两句吧...

相关阅读

相关 Insertion Sort List（C++对链表进行插入排序）

（1）插入排序 / Definition for singly-linked list. struct ListNode {

刺骨的言语ヽ痛彻心扉/ 2023年01月17日 08:59/ 0 赞/ 76 阅读

相关使用插入排序、归并排序对链表进行排序

/ Definition for singly-linked list. struct ListNode { int val

妖狐艹你老母/ 2022年12月23日 01:53/ 0 赞/ 198 阅读

相关 166-对链表进行插入排序

题目如下：对一条链表进行排序算法，要求使用算法为插入排序，且时间复杂度符合O(n^2) 解题方法： 1、判断链表是否为空，为空直接返回 2、新建排序链表头和尾都

电玩女神/ 2022年10月26日 12:52/ 0 赞/ 168 阅读

相关 leetcode 147. Insertion Sort List 链表插入排序

Sort a linked list using insertion sort. 本题就是要做链表的插入排序。代码如下： /class ListNode

矫情吗；*/ 2022年06月08日 04:58/ 0 赞/ 183 阅读

相关 [Leetcode][python]Insertion Sort List/对链表进行插入排序

题目大意通过插入排序的方法排序一个链表。解题思路参考：[http://www.cnblogs.com/zuoyuan/p/3700105.html][htt

古城微笑少年丶/ 2022年06月03日 03:00/ 0 赞/ 194 阅读

相关 5. insertion-sort-list 链表插入排序

题目描述 Sort a linked list using insertion sort. 对一个链表进行插入排序题目解析上一道题对链表进行归并排序和冒泡排

阳光穿透心脏的1/2处/ 2022年05月23日 11:24/ 0 赞/ 135 阅读

相关对一个链表进行插入排序

![这里写图片描述][70] class ListNode { int val; ListNode next;

灰太狼/ 2022年05月23日 02:50/ 0 赞/ 179 阅读

相关 LeetCode147. 对链表进行插入排序

对链表进行插入排序。 ![Insertion-sort-example-300px.gif][] 插入排序的动画演示如上。从第一个元素开始，该链表可以被认为已经部分排序（

电玩女神/ 2022年05月10日 08:38/ 0 赞/ 162 阅读

相关 LeetCode 147.Insertion Sort List (对链表进行插入排序)

题目描述：对链表进行插入排序。 ![Insertion-sort-example-300px.gif][] 插入排序的动画演示如上。从第一个元素开始，该链表可以被认为

川长思鸟来/ 2022年05月08日 13:33/ 0 赞/ 182 阅读

相关 Leetcode147. 对链表进行插入排序

题目描述 [https://leetcode-cn.com/problems/insertion-sort-list/description/][https_leetcod

缺乏、安全感/ 2021年09月27日 00:30/ 0 赞/ 298 阅读