AI summary
type
status
date
slug
summary
category
tags
icon
password
链表的分解
链表的分解技巧可以运用到很多单链表题目中，题目并不一定明确地要求你把链表分解成两部分，只要要求你从链表筛选出若干节点，都可以用这个技巧。
82. 删除排序链表中的重复元素 II
给定一个已排序的链表的头head， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。
把链表分解为重复的和不重复的两条。注意考虑重复的最后一个节点
p.val == dup.val；以及把虚拟头结点的值设为 101，与实际节点进行区分；还有最后要切断两条链表 dup.next, uniq.next = None, None。1836. 从未排序的链表中移除重复元素
给定一个链表的第一个节点head，找到链表中所有出现多于一次的元素，并删除这些元素所在的节点。返回删除后的链表。
遍历两次链表，第一次记录哪些值出现重复，然后第二次将无重复的节点分解出来。
链表的合并
有些题目虽然不是链表的题目，但其中蕴含了合并有序链表的思想。
264. 丑数 II
给你一个整数n，请你找出并返回第n个 丑数 。丑数 就是质因子只包含2、3和5的正整数。
一道数学题，用到了筛选素数的思路。
如果一个数
x 是丑数，那么 x * 2, x * 3, x * 5 都一定是丑数。代码挺妙的，不重不漏，可以理解记忆一下。
378. 有序矩阵中第 K 小的元素
给你一个n x n矩阵matrix，其中每行和每列元素均按升序排序，找到矩阵中第k小的元素。请注意，它是 排序后 的第k小元素，而不是第k个 不同 的元素。你必须找到一个内存复杂度优于 的解决方案。
这道题其实是前文讲过的 23. 合并K个升序链表 的变体。
矩阵中的每一行都是排好序的，就好比多条有序链表，你用优先级队列施展合并多条有序链表的逻辑就能找到第
k 小的元素了。373. 查找和最小的 K 对数字
给定两个以 非递减顺序排列 的整数数组nums1和nums2, 以及一个整数k。定义一对值(u,v)，其中第一个元素来自nums1，第二个元素来自nums2。请找到和最小的k个数对(u1,v1),(u2,v2)...(uk,vk)。
怎么把这道题变成合并多个有序链表呢？就比如说题目输入的用例：
nums1 = [1,7,11], nums2 = [2,4,6]组合出的所有数对儿这就可以抽象成三个有序链表：
这三个链表中每个元素（数对之和）是递增的，所以就可以按照 23. 合并K个升序链表 的思路来合并，取出前
k 个作为答案即可。链表运算题
2. 两数相加
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。请你将两个数相加，并以相同形式返回一个表示和的链表。你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
逆序存储很友好了，直接遍历链表就是从个位开始的，符合我们计算加法的习惯顺序。如果是正序存储，那倒要费点脑筋了，可能需要 翻转链表 或者使用栈来辅助。
这道题主要考察对进位的处理。注意这个
carry 变量的处理，在我们手动模拟加法过程的时候会经常用到。代码中还用到一个链表的算法题中是很常见的「虚拟头结点」技巧，也就是
dummy 节点。有了 dummy 节点这个占位符，可以避免处理初始的空指针情况，降低代码的复杂性。445. 两数相加 II
给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。你可以假设除了数字 0 之外，这两个数字都不会以零开头。进阶：如果输入链表不能翻转该如何解决？
可以利用栈这种先进后出的数据结构，把链表节点从头到尾放进栈中，再从栈拿出来就是从尾到头的顺序，相当于是反转链表的效果，然后又回到了第 2 题的加法逻辑。
还有一个需要注意的是，计算结果的高位也应该放在结果链表的左侧，也就是头插法。