下载掌阅APP，畅读海量书库
立即打开
【问题描述】 给定一个已排序的链表head，删除其中所有重复的元素，使每个元素只出现一次，返回已排序的链表。
例如，head=[1，1，2，3，3，3]，删除所有重复的元素后head=[1，2，3]，如图2.26所示。
图2.26 删除重复元素
【限制】 链表中结点的数目在[0，300]范围内，-100≤Node.val≤100，题目数据保证链表已经按升序排列。
【解法1】
直接删除法
。由于head是递增有序的，所以值相同的结点是相邻排列的。用同步指针（pre，p）从头开始遍历head，当p!=NULL时循环：若p-
val=pre-
val，则通过结点pre删除结点p，保持pre不动，让p指向结点pre的后继结点后继续循环，否则让pre、p同步后移一个结点后继续循环。最后返回head。
【解法2】
尾插法
。先创建只含首结点的结果单链表head，r为尾结点指针，用p遍历head的剩余结点，当p-
val≠p-
val时说明结点p是非重复结点，将其链接到head的末尾，然后p后移一个结点，否则直接让p后移一个结点。最后将尾结点的next域置为空，并返回head。
【问题描述】 给定一个已排序的链表head，删除原始链表中所有重复的元素，只留下不同的元素，返回已排序的链表。
例如，head=[1，2，3，3，4，4，5]，其中3和4是重复的元素，删除后head=[1，2，5]，如图2.27所示。
【限制】 链表中结点的数目在[0，300]范围内，-100≤Node.val≤100，题目数据保证链表已经按升序排列。
图2.27 删除重复元素Ⅱ
【解法1】
用尾插法建表
。设置一个计数器数组cnt，用cnt[100+p-
val]记录结点p值出现的次数（加上100的目的是保证数组下标为非负整数），创建一个带头结点的空单链表h，用p遍历head，若cnt[100+p-
val]=1，说明结点p是非重复结点，将其链接到链表h的末尾，否则p后移一个结点。最后将尾结点r的next域置为空，并返回h-
next。对应的算法如下。
C++：
提交运行：
Python：
提交运行：
【解法2】
直接删除法
。为链表head增加一个头结点h，首先pre指向头结点，p指向其后继结点，在p不为空时循环：置q=p-
next。
（1）若q不为空并且q-
val=p-
val，说明结点p是重复结点，让q继续后移到第一个不等于p-
val的结点，通过pre结点将结点p和结点q之间的全部重复结点删除，删除后pre不变，p指向其后继结点q，如图2.28所示。
（2）否则说明结点p是非重复结点，保留该结点，让pre和p同步后移一个结点。
最后返回h-
next。
图2.28 删除重复结点的过程
对应的算法如下。
C++：
提交运行：
Python：
提交运行：
【问题描述】 将两个升序链表合并为一个新的升序链表并返回，新链表是通过拼接给定的两个链表的所有结点组成的。
例如，list1=[1，2，4]，list2=[1，3，4]，合并的链表list=[1，1，2，3，4，4]。
【限制】 两个链表的结点数目的范围是[0，50]，-100≤Node.val≤100，list1和list2均按非递减顺序排列。
【解题思路】 二路归并法 。使用2.1.2节中两个有序链表合并的方法，这里要求新链表是通过拼接给定的两个链表的所有结点组成的，所以不能使用结点复制的方法，而是直接将归并的结点链接起来构成结构链表。将两个长度分别为 m 和 n 的有序链表合并为一个有序链表的时间复杂度为 O （ m + n ）。对应的算法如下。
C++：
提交运行：
Python：
提交运行：
【问题描述】 给定一个链表数组，每个链表都已经按升序排列，请将所有链表合并到一个升序链表中，返回合并后的链表。
例如，lists=[[1，4，5]，[1，3，4]，[2，6]]，合并后的链表为[1，1，2，3，4，4，5，6]。
【限制】 k =lists.length，0≤ k ≤10 4 ，0≤lists[ i ].length≤500，-10 4 ≤lists[ i ][ j ]≤10 4 ，lists[ i ]按升序排列，lists[ i ].length的总和不超过10 4 。
【解法1】 二路归并法 + 用尾插法建表 。先置结果链表h为lists[0]，然后依次将h与lists[ i ]做二路归并，归并的结果仍然存放在h中，其中二路归并算法同2.4.3节，最后返回h即可。
设 k 个有序链表的编号为0～ k -1，链表 i 的长度（结点的个数）为 n i （0≤ i ≤ k -1）， n = n 0 + n 1 +…+ n k -1 ，本解法的执行时间为 T （ n ）=（ n 0 + n 1 ）+（ n 0 + n 1 + n 2 ）+…+（ n 0 + n 1 +…+ n k -1 ）= kn 0 +（ k -1） n 1 +…+ n k -1 。当 n i 均相同（即 n i = n / k ）时，可以推出 T （ n ）= O （ kn ）。
对应的算法如下。
C++：
提交运行：
Python：
提交运行：
【解法2】
k
路归并法
+
用尾插法建表
。先创建一个空的结果单链表h（r为其尾结点指针）。设置一个长度为
k
的数组
x
，用lists[
i
]（0≤
i
≤
k
-1）遍历链表
i
的结点，
x
[
i
]取lists[
i
]指向的结点的值（当lists[
i
]为空时置
x
[
i
]为∞），每次通过简单选择方法在
x
中找出最小元素
x
[mini]（表示最小结点是链表mini的结点），若
x
[mini]=∞，说明全部结点归并完毕，返回h-
next，否则将lists[mini]结点链接到
h
的末尾，后移lists[mini]指针，同时
x
[mini]取lists[mini]指向的结点的值（当lists[mini]为空时置
x
[mini]为∞）。
设 k 个有序链表的编号为0～ k -1，链表 i 的长度（结点的个数）为 n i （0≤ i ≤ k -1）， n = n 0 + n 1 +…+ n k -1 ，通过简单选择方法在 x 中找出最小元素的时间为 O （ k ），本解法的执行时间为 T （ n ）=（ n 0 + n 1 +…+ n k -1 ） O （ k ）= O （ kn ）。
对应的算法如下。
C++：
提交运行：
说明： 解法2的运行时间超过解法1的运行时间，在解法2中可以通过小根堆找 x 中的最小元素，以大幅度提高时间性能，参见9.3.3节。
Python：
提交运行：
【问题描述】 多项式链表是一种特殊形式的链表，每个结点表示多项式的一项。每个结点有3个属性：coefficient为该项的系数，如项9 x 4 的系数是9；power为该项的指数，如项9 x 4 的指数是4；next为指向下一个结点的指针（引用），如果当前结点为链表的最后一个结点，则为空。例如，多项式5 x 3 +4 x -7可以表示成如图2.29所示的多项式链表。
图2.29 一个多项式链表
多项式链表必须是标准形式的，即多项式必须严格按指数power的递减顺序排列（即降幂排列）。另外，系数coefficient为0的项需要省略。给定两个多项式链表的首结点poly1和poly2，以多项式链表形式返回它们的和。
PolyNode格式：输入/输出格式表示为 n 个结点的列表，其中每个结点表示为[coefficient，power]，如多项式5 x 3 +4 x -7表示为[[5，3]，[4，1]，[-7，0]]。
例如，两个多项式poly1=[[2，2]，[4，1]，[3，0]]，poly2=[[3，2]，[-4，1]，[-1，0]]，poly1=2 x 2 +4 x +3，poly2=3 x 2 -4 x -1，poly1和poly2的和为5 x 2 +2，所以答案为[[5，2]，[2，0]]。
PolyNode的类型如下。
C++：
Python：
【限制】 0≤ n ≤10 4 ，-10 9 ≤PolyNode.coefficient≤10 9 ，PolyNode.coefficient≠0，0≤PolyNode.power≤10 9 ，PolyNode.power＞PolyNode.next.power。
【解题思路】 二路归并法 + 用尾插法建表 。先创建一个空的结果单链表h（r为其尾结点指针）。用p和q分别遍历poly1和poly2，当p和q均不为空时循环：
（1）若p-
power＞q-
power，归并结点p，由结点p复制产生结点s，将结点s链接到h的末尾，后移结点指针p。
（2）若p-
power＜q-
power，归并结点q，由结点q复制产生结点s，将结点s链接到h的末尾，后移结点指针q。
（3）若p-
power=q-
power，求出结点p与结点q的系数和
c
，如果
c
≠0，由
c
和结点p的指数复制产生结点s，将结点s链接到h的末尾，后移结点指针p和q。
循环结束后将剩余的所有结点复制后链接到h的末尾。最后返回h-
next。