给定两个有序链表的头指针head1和head2，打印两个链表的公共部分

最大值减去最小值小于或等于num的子数组数量

【题目】

给定数组arr和整数num，共返回有多少个子数组满足如下情况：

max(arr[i..j]) - min(arr[i..j]) <= num

max(arr[i..j])表示子数组arr[i..j]中的最大值，min(arr[i..j])表示子数组arr[i..j]中的最小值。

【要求】

如果数组长度为N ，请实现时间复杂度为O (N )的解法。

【难度】

校　★★★☆

【解答】

首先介绍普通的解法，找到arr的所有子数组，一共有O (N 2 )个，然后对每一个子数组做遍历找到其中的最小值和最大值，这个过程时间复杂度为O (N )，然后看看这个子数组是否满足条件。统计所有满足的子数组数量即可。普通解法容易实现，但是时间复杂度为O (N 3 )，本书不再详述。最优解可以做到时间复杂度O (N )，额外空间复杂度O (N )，在阅读下面的分析过程之前，请读者先阅读本章“生成窗口最大值数组”问题，本题所使用到的双端队列结构与解决“生成窗口最大值数组”问题中的双端队列结构含义基本一致。

生成两个双端队列qmax和qmin。当子数组为arr[i..j]时，qmax维护了窗口子数组arr[i..j]的最大值更新的结构，qmin维护了窗口子数组arr[i..j]的最小值更新的结构。当子数组arr[i..j]向右扩一个位置变成arr[i..j+1]时，qmax和qmin结构可以在O (1)的时间内更新，并且可以在O (1)的时间内得到arr[i..j+1]的最大值和最小值。当子数组arr[i..j]向左缩一个位置变成arr[i+1..j]时，qmax和qmin结构依然可以在O (1)的时间内更新，并且在O (1)的时间内得到arr[i+1..j]的最大值和最小值。

通过分析题目满足的条件，可以得到如下两个结论：

●　如果子数组arr[i..j]满足条件，即max(arr[i..j])-min(arr[i..j])<=num，那么arr[i..j]中的每一个子数组，即arr[k..l](i<=k<=l<=j)都满足条件。我们以子数组arr[i..j-1]为例说明，arr[i..j-1]最大值只可能小于或等于arr[i..j]的最大值，arr[i..j-1]最小值只可能大于或等于arr[i..j]的最小值，所以arr[i..j-1]必然满足条件。同理，arr[i..j]中的每一个子数组都满足条件。

●　如果子数组arr[i..j]不满足条件，那么所有包含arr[i..j]的子数组，即arr[k..l](k<=i<=j<=l)都不满足条件。证明过程同第一个结论。

根据双端队列qmax和qmin的结构性质，以及如上两个结论，设计整个过程如下：

1．生成两个双端队列qmax和qmin，含义如上文所说。生成两个整型变量i和j，表示子数组的范围，即arr[i..j]。生成整型变量res，表示所有满足条件的子数组数量。

2．令j不断向右移动（j++），表示arr[i..j]一直向右扩大，并不断更新qmax和qmin结构，保证qmax和qmin始终维持动态窗口最大值和最小值的更新结构。一旦出现arr[i..j]不满足条件的情况，j向右扩的过程停止，此时arr[i..j-1]、arr[i..j-2]、arr[i..j-3]、...、arr[i..i]一定都是满足条件的。也就是说，所有必须以arr[i]作为第一个元素的子数组，满足条件的数量为j -i 个。于是令res+=j-i。

3．当进行完步骤2，令i向右移动一个位置，并对qmax和qmin做出相应的更新，qmax和qmin从原来的arr[i..j]窗口变成arr[i+1..j]窗口的最大值和最小值的更新结构。然后重复步骤2，也就是求所有必须以arr[i+1]作为第一个元素的子数组中，满足条件的数量有多少个。

4．根据步骤2和步骤3，依次求出以arr[0]、arr[1]、...、arr[N-1]作为第一个元素的子数组中满足条件的数量分别有多少个，累加起来的数量就是最终的结果。

上述过程中，所有的下标值最多进qmax和qmin一次，出qmax和qmin一次。i和j的值也不断增加，并且从来不减小。所以整个过程的时间复杂度为O (N )。

最优解全部实现请参看如下代码中的getNum方法。

public int getNum(int[] arr, int num) { if (arr == null || arr.length == 0) { return 0; } LinkedListqmin = new LinkedList(); LinkedListqmax = new LinkedList(); int i = 0; int j = 0; int res = 0; while (i < arr.length) { while (j < arr.length) { while (! qmin.isEmpty() && arr[qmin.peekLast()] >= arr[j]) { qmin.pollLast(); } qmin.addLast(j); while (! qmax.isEmpty() && arr[qmax.peekLast()] <= if="" -=""> num) { break; } j++; } if (qmin.peekFirst() == i) { qmin.pollFirst(); } if (qmax.peekFirst() == i) { qmax.pollFirst(); } res += j - i; i++; } return res; }

第2 章

链表问题

打印两个有序链表的公共部分

【题目】

给定两个有序链表的头指针head1和head2，打印两个链表的公共部分。

【难度】

士　★☆☆☆

【解答】

本题难度很低，因为是有序链表，所以从两个链表的头开始进行如下判断：

●　如果head1的值小于head2，则head1往下移动。

●　如果head2的值小于head1，则head2往下移动。

●　如果head1的值与head2的值相等，则打印这个值，然后head1与head2都往下移动。

●　head1或head2有任何一个移动到null，整个过程停止。

具体过程参看如下代码中的printCommonPart方法。

public class Node { public int value; public Node next; public Node(int data) { this.value = data; } } public void printCommonPart(Node head1, Node head2) { System.out.print("Common Part: "); while (head1 ! = null && head2 ! = null) { if (head1.value < head2.value) { head1 = head1.next; } else if (head1.value > head2.value) { head2 = head2.next; } else { System.out.print(head1.value + " "); head1 = head1.next; head2 = head2.next; } } System.out.println(); }

在单链表和双链表中删除倒数第K 个节点

【题目】

分别实现两个函数，一个可以删除单链表中倒数第K 个节点，另一个可以删除双链表中倒数第K 个节点。

【要求】

如果链表长度为N ，时间复杂度达到O (N )，额外空间复杂度达到O (1)。

【难度】

士　★☆☆☆

【解答】

本题较为简单，实现方式也是多种多样的，本书提供一种方法供读者参考。

先来看看单链表如何调整。如果链表为空或者K 值小于1，这种情况下，参数是无效的，直接返回即可。除此之外，让链表从头开始走到尾，每移动一步，就让K 的值减1。

链表：1->2->3，K = 4，链表根本不存在倒数第4个节点。

走到的节点：1 -> 2 -> 3

K 变化为：321

链表：1->2->3，K = 3，链表倒数第3个节点是1节点。

走到的节点：1 -> 2 -> 3

K 变化为：210

链表：1->2->3，K = 2，链表倒数第2个节点是2节点。

走到的节点：1 -> 2 -> 3

K 变化为：1 0 -1

由以上三种情况可知，让链表从头开始走到尾，每移动一步，就让K 值减1，当链表走到结尾时，如果K 值大于0，说明不用调整链表，因为链表根本没有倒数第K 个节点，此时将原链表直接返回即可；如果K 值等于0，说明链表倒数第K 个节点就是头节点，此时直接返回head.next，也就是原链表的第二个节点，让第二个节点作为链表的头返回即可，相当于删除头节点；接下来，说明一下如果K 值小于0，该如何处理。

先明确一点，如果要删除链表的头节点之后的某个节点，实际上需要找到要删除节点的前一个节点，比如：1->2->3，如果想删除节点2，则需要找到节点1，然后把节点1连到节点3上（1->3），以此来达到删除节点2的目的。