【Leetcode Daily】147对链表进行插入排序

发表于2026-01-01|更新于2026-01-01|力扣日常 | LeetcodeDaily

|总字数:294|阅读时长:1分钟|浏览量:

题目浅析

想查看原题可以点击题目链接。
简单地说，就是给一个链表，要对这个链表做插入排序。

思路分享

只能遍历链表，留一个哨兵节点，因为头节点也可能更换。
把第一个节点当成已遍历的节点，一个个向后，如果新遇到的节点值比最后一个已遍历节点更大，这个好办，就直接插后面；
但如果新的节点值更少，那就得从头遍历找到合适的位置插入。这里的插入处理起来很是要注意，很容易把指针指错。

https://leetcode.cn/problems/insertion-sort-list/solutions/491124/dui-lian-biao-jin-xing-cha-ru-pai-xu-by-leetcode-s/

代码解答（强烈建议自行解答后再看）

参考题解

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def insertionSortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head:
            return head
        
        sentinal = ListNode(0, head)
        cur = head
        last_sorted = head
        while cur.next:
            cur = cur.next
            if cur.val < last_sorted.val:
                pre = sentinal
                while pre.next.val < cur.val:
                    pre = pre.next
                last_sorted.next = cur.next
                insert_next = pre.next
                pre.next = cur
                cur.next = insert_next
            else:
                last_sorted = last_sorted.next
            cur = last_sorted

        return sentinal.next

文章作者: 陆爻齐-LuYaoQi

文章链接: http://hslix.github.io/posts/fa3c2333.html

版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 LuYaoQi's Blogs！

Algorithm 链表

相关推荐

【Leetcode Daily】1290二进制链表转整数

题目浅析想查看原题可以点击题目链接。简单地说，就是用链表存储二进制数，现在给你链表，请你给出所代表的二进制数的十进制表现。思路分享二进制转十进制的方法很简单，起始为 0，取数加上去，乘二，再取数加上去直到取尽。至于遍历链表，只要 head ！= None，head = head.next 即可。 https://leetcode.cn/problems/convert-binary-number-in-a-linked-list-to-integer/solutions/3723060/bian-li-lian-biao-pythonjavaccgojsrust-b-ykjd/ 代码解答（强烈建议自行解答后再看）参考题解 12345678910111213# Definition for singly-linked list.# class ListNode:# def __init__(self, val=0, next=None):# self.val = val# self.next =...

【Leetcode Daily】1351负数有序矩阵中的负数

题目浅析想查看原题可以点击题目链接。简单地说，就是给一个行列都是非升序排列的数组，其中整数可正可负，求整个数组的负数个数。思路分享利用行列皆非升序排列，可以从数组的右上角开始排查，求出每一列的负数个数，然后到了下一行，负数的个数不可能更少，这样复杂度就成了O（m+n） https://leetcode.cn/problems/count-negative-numbers-in-a-sorted-matrix/solutions/3861108/tu-jie-zuo-fa-tong-240-ti-yi-tu-miao-don-vovs/?envType=daily-question&envId=2025-12-28 代码解答（强烈建议自行解答后再看）参考题解 123456789101112131415class Solution: def countNegatives(self, grid: List[List[int]]) -> int: m, n = len(grid), len(grid[0]) ans...

【Leetcode Daily】1669合并两个链表

题目浅析想查看原题可以点击题目链接。简单地说，就是给两个链表，将一个链表代替另一个链表的中间一段，返回合并后的链表。思路分享就是找到要删除区间的前一个节点和中间的最后一个节点，这两个节点的 next 分别是要插入链表的起点和终点，如此就插好了。 https://leetcode.cn/problems/merge-in-between-linked-lists/solutions/3820116/ling-shen-ti-dan-qing-xi-ti-jie-by-pure-11575/ 代码解答（强烈建议自行解答后再看）参考题解 12345678910111213141516171819# Definition for singly-linked list.# class ListNode:# def __init__(self, val=0, next=None):# self.val = val# self.next = nextclass Solution: def...

【Leetcode Daily】2058找出临界点之间的最小和最大距离

题目浅析想查看原题可以点击题目链接。简单地说，就是给一个长度至少为二的链表，其中可能存在局部的极大点或者极小点，返回极值点之间的最小距离和最大距离思路分享用 first 和 last 记录已经遍历到的最早和最晚的极值点，那么最大距离就是这两个之差，但是最小距离需要实时计算，每次可以拿新的极值点与 last 做差更新。 https://leetcode.cn/problems/find-the-minimum-and-maximum-number-of-nodes-between-critical-points/solutions/1075991/go-mo-ni-bian-li-lian-biao-bian-li-lin-j-rx9s/ 代码解答（强烈建议自行解答后再看）参考题解 123456789101112131415161718192021# Definition for singly-linked list.# class ListNode:# def __init__(self, val=0, next=None):# ...

【Leetcode Daily】2181合并零之间的节点

题目浅析想查看原题可以点击题目链接。简单地说，就是给一个链表，将其中两个为零的节点之间的节点合成一个节点，节点和为其值。思路分享我的思路是单指针遍历节点，将遇到非零值纳入新链表；灵茶山艾府的方法是双指针，一个指针指第一个 0，另一个指针向后遍历，遇到的非零值加到第一个指针上，遇到零则更新第一个指针到第二个指针的位置，直接原地修改。 https://leetcode.cn/problems/merge-nodes-in-between-zeros/ 代码解答（强烈建议自行解答后再看）参考题解 123456789101112131415161718192021222324252627282930313233# Definition for singly-linked list.# class ListNode:# def __init__(self, val=0, next=None):# self.val = val# self.next = nextclass Solution: def...

【Leetcode Daily】237删除链表中的节点

题目浅析想查看原题可以点击题目链接。简单地说，就是在不给链表头的情况下，仅给要删除的节点，如何实现删除。（链表长度至少为 2，且删除节点不在队尾）思路分享正如灵神所说，真是脑筋急转弯，由于检测是否删除靠得是输出值，所以只要把要删除节点的值换成下一个节点，并把 next 跳过下一个就行。 https://leetcode.cn/problems/delete-node-in-a-linked-list/solutions/2004056/ru-he-shan-chu-jie-dian-liu-fen-zhong-ga-x3kn/ 代码解答（强烈建议自行解答后再看）参考题解 1234567891011121314# Definition for singly-linked list.# class ListNode:# def __init__(self, x):# self.val = x# self.next = Noneclass Solution: def deleteNode(self, node): ...

数据加载中