链表的合并
有些题目虽然不是链表的题目，但其中蕴含了合并有序链表的思想。
264. 丑数 II 力扣
给你一个整数 n ，请你找出并返回第 n 个 丑数 。
丑数 就是质因子只包含 2、3 和 5 的正整数。
示例 1：
输入：n = 10
输出：12
解释：[1, 2, 3, 4, 5, 6, 8, 9, 10, 12] 是由前 10 个丑数组成的序列。
示例 2：
输入：n = 1
输出：1
解释：1 通常被视为丑数。
提示：
1 <= n <= 1690
基本思路
这道题很精妙，你看着它好像是道数学题，实际上它却是一个合并多个有序链表的问题，同时用到了筛选素数的思路。
根据题意，每个丑数都可以由其他较小的丑数通过乘以 2 或 3 或 5 得到。
我们把所有丑数想象成一个从小到大排序的链表，就是这个样子：
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 8 -> ...然后，我们可以把丑数分为三类：2 的倍数、3 的倍数、5 的倍数（按照题目的意思，1 算作特殊的丑数，放在开头），这三类丑数就好像三条有序链表，如下：
能被 2 整除的丑数：
1 -> 1*2 -> 2*2 -> 3*2 -> 4*2 -> 5*2 -> 6*2 -> 8*2 ->...能被 3 整除的丑数：
1 -> 1*3 -> 2*3 -> 3*3 -> 4*3 -> 5*3 -> 6*3 -> 8*3 ->...能被 5 整除的丑数：
1 -> 1*5 -> 2*5 -> 3*5 -> 4*5 -> 5*5 -> 6*5 -> 8*5 ->...我们其实就是想把这三条有序链表一起并去重，合并的结果就是丑数的序列。然后求合并后的这条有序链表中第 n 个元素是什么。所以这里就和合并多个有序链表一样
具体思路看注释吧
class Solution:
def nthUglyNumber(self, n: int) -> int:
# 可以理解为三个指向有序链表头结点的指针，p2,p3,p5代表的是第几个数的 2 倍、第几个数 3 倍、第几个数 5 倍
p2, p3, p5 = 1, 1, 1
# 可以理解为三个有序链表的头节点的值
product2, product3, product5 = 1, 1, 1
# 可以理解为最终合并的有序链表（结果链表）
ugly = [0] * (n + 1)
# 可以理解为结果链表上的指针
p = 1
# 开始合并三个有序链表
while p <= n:
# 取三个链表的最小结点
min_val = min(product2, product3, product5)
# 接到结果链表上
ugly[p] = min_val
p += 1
# 前进对应有序链表上的指针
if min_val == product2:
product2 = 2 * ugly[p2]
p2 += 1
if min_val == product3:
product3 = 3 * ugly[p3]
p3 += 1
if min_val == product5:
product5 = 5 * ugly[p5]
p5 += 1
# 返回第 n 个丑数
return ugly[n]链表运算题
有些题目虽然不是链表的题目，但其中蕴含了合并有序链表的思想。
445. 两数相加 II 力扣
给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。
你可以假设除了数字 0 之外，这两个数字都不会以零开头。
示例1：
输入：l1 = [7,2,4,3], l2 = [5,6,4]
输出：[7,8,0,7]
示例2：
输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[8,0,7]
示例3：
输入：l1 = [0], l2 = [0]
输出：[0]
提示：
链表的长度范围为 [1, 100]
0 <= node.val <= 9
输入数据保证链表代表的数字无前导 0
进阶：如果输入链表不能翻转该如何解决？
基本思路
这道题是 两数相加 的进阶问题，我们模拟加法运算当然是从最低位开始加，这样才能正确的处理进位。但现在单链表的开头是最高位，那么最直接的想法就是先 翻转链表，这样就没什么难度。
不过本题也说了，如果不让你反转链表怎么办？其实也好办，我们可以利用栈这种先进后出的数据结构，把链表节点从头到尾放进栈中，再从栈拿出来就是从尾到头的顺序，相当于是反转链表的效果，然后再进行加法运算即可。
还有一个需要注意的是，计算结果的高位也应该放在结果链表的左侧，也就是插入到 dummy 节点的后面。具体看代码吧。
class Solution:
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
# 把链表元素转入栈中
stk1 = []
while l1:
stk1.append(l1.val)
l1 = l1.next
stk2 = []
while l2:
stk2.append(l2.val)
l2 = l2.next
# 接下来基本上是复用我在第 2 题的代码逻辑
# 注意新节点要直接插入到 dummy 后面
# 虚拟头结点（构建新链表时的常用技巧）
dummy = ListNode(-1)
# 记录进位
carry = 0
# 开始执行加法，两条链表走完且没有进位时才能结束循环
while stk1 or stk2 or carry > 0:
# 先加上上次的进位
val = carry
if stk1:
val += stk1.pop()
if stk2:
val += stk2.pop()
# 处理进位情况
carry = val // 10
val = val % 10
# 构建新节点，直接接在 dummy 后面
newNode = ListNode(val)
newNode.next = dummy.next
dummy.next = newNode
# 返回结果链表的头结点（去除虚拟头结点）
return dummy.next
