第二章：链表问题（三）
将单向链表按某值划分成左边小、中间相等、右边大的形式
【题目】
给定一个单向链表的头节点head，节点的值类型是整型，再给定一个整数pivot。实现一个调整链表的函数，将链表调整为左部分都是值小于pivot的节点，中间部分都是值等于pivot的节点，右部分都是值大于pivot的节点。除这个要求外，对调整后的节点顺序没有更多的要求。
例如：链表9->0->4->5->1，pivot=3。
调整后链表可以是1->0->4->9->5，也可以是0->1->9->5->4。总之，满足左部分都是小于3的节点，中间部分都是等于3的节点（本例中这个部分为空），右部分都是大于3的节点即可。对某部分内部的节点顺序不做要求。
进阶：
在原问题的要求之上再增加如下两个要求。
— 在左、中、右三个部分的内部也做顺序要求，要求每部分里的节点从左到右的顺序与原链表中节点的先后次序一致。
例如：链表9->0->4->5->1，pivot=3。调整后的链表是0->1->9->4->5。在满足原问题要求的同时，左部分节点从左到右为0、1。在原链表中也是先出现0，后出现1；中间部分在本例中为空，不再讨论；右部分节点从左到右为9、4、5。在原链表中也是先出现9，然后出现4，最后出现5。
— 如果链表长度为N，时间复杂度请达到O(N)，额外空间复杂度请达到O(1)。
【难度】
尉 ★★☆☆
【解答】
普通解法的时间复杂度为O(N)，额外空间复杂度为O(N)，就是把链表中的所有节点放入一个额外的数组中，然后统一调整位置的办法。具体过程如下：
1．先遍历一遍链表，为了得到链表的长度，假设长度为N。
2．生成长度为N的Node类型的数组nodeArr，然后遍历一次链表，将节点依次放进nodeArr中。本书在这里不用LinkedList或ArrayList等Java提供的结构，因为一个纯粹的数组结构比较利于步骤3的调整。
3．在nodeArr中把小于pivot的节点放在左边，把相等的放中间，把大于的放在右边。也就是改进了快速排序中partition的调整过程，即如下代码中的arrPartition方法。实现的具体解释请参看本书“数组类似partition的调整”问题，这里不再详述。
4．经过步骤3的调整后，nodeArr是满足题目要求的节点顺序，只要把nodeArr中的节点依次重连起来即可，整个过程结束。
全部过程请参看如下代码中的listPartition1方法。
public class Node {
public int value;
public Node next;
public Node(int data) {
this.value = data;
}
}
public Node listPartition1(Node head, int pivot) {
if (head == null) {
return head;
}
Node cur = head;
int i = 0;
while (cur != null) {
i++;
cur = cur.next;
}
Node[] nodeArr = new Node[i];
i = 0;
cur = head;
for (i = 0; i != nodeArr.length; i++) {
nodeArr[i] = cur;
cur = cur.next;
}
arrPartition(nodeArr, pivot);
for (i = 1; i != nodeArr.length; i++) {
nodeArr[i - 1].next = nodeArr[i];
}
nodeArr[i - 1].next = null;
return nodeArr[0];
}
public void arrPartition(Node[] nodeArr, int pivot) {
int small = -1;
int big = nodeArr.length;
int index = 0;
while (index != big) {
if (nodeArr[index].value < pivot) {
swap(nodeArr, ++small, index++);
} else if (nodeArr[index].value == pivot) {
index++;
} else {
swap(nodeArr, --big, index);
}
}
}
public void swap(Node[] nodeArr, int a, int b) {
Node tmp = nodeArr[a];
nodeArr[a] = nodeArr[b];
nodeArr[b] = tmp;
}
下面来看看增加要求之后的进阶解法。对每部分都增加了节点顺序要求，同时时间复杂度仍然为O(N)，额外空间复杂度为O(1)。既然额外空间复杂度为O(1)，说明实现时只能使用有限的几个变量来完成所有的调整。
进阶解法的具体过程如下：
1．将原链表中的所有节点依次划分进三个链表，三个链表分别为small代表左部分，equal代表中间部分，big代表右部分。
例如，链表7->9->1->8->5->2->5，pivot=5。在划分之后，small、equal、big分别为：
small：1->2->null
equal：5->5->null
big：7->9->8->null
2．将small、equal和big三个链表重新串起来即可。
3．整个过程需要特别注意对null节点的判断和处理。
进阶解法主要还是考查面试者利用有限几个变量调整链表的代码实现能力，全部进阶解法请参看如下代码中的listPartition2方法。
public static Node listPartition2(Node head, int pivot) {
Node sH = null; // 小的头
Node sT = null; // 小的尾
Node eH = null; // 相等的头
Node eT = null; // 相等的尾
Node bH = null; // 大的头
Node bT = null; // 大的尾
Node next = null; // 保存下一个节点
// 所有的节点分进三个链表中
while (head != null) {
next = head.next;
head.next = null;
if (head.value < pivot) {
if (sH == null) {
sH = head;
sT = head;
} else {
sT.next = head;
sT = head;
}
} else if (head.value == pivot) {
if (eH == null) {
eH = head;
eT = head;
} else {
eT.next = head;
eT = head;
}
} else {
if (bH == null) {
bH = head;
bT = head;
} else {
bT.next = head;
bT = head;
}
}
head = next;
}
// 小的和相等的重新连接
if (sT != null) {
sT.next = eH;
eT = eT == null ? sT : eT;
}
// 所有的重新连接
if (eT != null) {
eT.next = bH;
}
return sH != null ? sH : eH != null ? eH : bH;
}
复制含有随机指针节点的链表
【题目】
一种特殊的链表节点类描述如下：
public class Node {
public int value;
public Node next;
public Node rand;
public Node(int data) {
this.value = data;
}
}
Node类中的value是节点值，next指针和正常单链表中next指针的意义一样，都指向下一个节点，rand指针是Node类中新增的指针，这个指针可能指向链表中的任意一个节点，也可能指向null。
给定一个由Node节点类型组成的无环单链表的头节点head，请实现一个函数完成这个链表中所有结构的复制，并返回复制的新链表的头节点。例如：链表1->2->3->null，假设1的rand指针指向3，2的rand指针指向null，3的rand指针指向1。复制后的链表应该也是这种结构，比如，1¢->2¢->3¢->null，1¢的rand指针指向3¢，2¢的rand指针指向null，3¢的rand指针指向1¢，最后返回1¢。
进阶：不使用额外的数据结构，只用有限几个变量，且在时间复杂度为O(N)内完成原问题要实现的函数。
【难度】
尉 ★★☆☆
【解答】
首先介绍普通解法，普通解法可以做到时间复杂度为O(N)，额外空间复杂度为O(N)，需要使用到哈希表（HashMap）结构。具体过程如下：
1．从左到右遍历链表，对每个节点都复制生成相应的副本节点，然后将对应关系放入哈希表map中。例如，链表1->2->3->null，遍历1、2、3时依次生成1¢、2¢、3¢，最后将对应关系放入map中。
| key | value | 意 义 |
| 1 | 1¢ | 表示节点1复制了节点1¢ |
| 2 | 2¢ | 表示节点2复制了节点2¢ |
| 3 | 3¢ | 表示节点3复制了节点3¢ |
步骤1完成后，原链表没有任何变化，每一个副本节点的next和rand指针都指向null。
2．再从左到右遍历链表，此时就可以设置每一个副本节点的next和rand指针。
例如：原链表1->2->3->null，假设1的rand指针指向3，2的rand指针指向null，3的rand指针指向1。遍历到节点1时，可以从map中得到节点1的副本节点1¢，节点1的next指向节点2，所以从map中得到节点2的副本节点2¢，然后令1¢.next=2¢，副本节点1¢的next指针就设置好了。同时节点1的rand指向节点3，所以从map中得到节点3的副本节点3¢，然后令1¢.rand=3¢，副本节点1¢的rand指针也设置好了。以这种方式可以设置每一个副本节点的next与rand指针。
3．将1¢节点作为结果返回即可。
哈希表增删改查的操作时间复杂度都是O(1)，普通方法一共只遍历链表两遍，所以普通解法的时间复杂度为O(N)，因为使用了哈希表来保存原节点与副本节点的对应关系，所以额外空间复杂度为O(N)。
具体过程请参看如下代码中的copyListWithRand1方法。
public Node copyListWithRand1(Node head) {
HashMap<Node, Node> map = new HashMap<Node, Node>();
Node cur = head;
while (cur != null) {
map.put(cur, new Node(cur.value));
cur = cur.next;
}
cur = head;
while (cur != null) {
map.get(cur).next = map.get(cur.next);
map.get(cur).rand = map.get(cur.rand);
cur = cur.next;
}
return map.get(head);
}
接下来介绍进阶解法，进阶解法不使用哈希表来保存对应关系，而只用有限的几个变量完成所有的功能。具体过程如下：
1．从左到右遍历链表，对每个节点cur都复制生成相应的副本节点copy，然后把copy放在cur和下一个要遍历节点的中间。
例如：原链表1->2->3->null，在步骤1中完成后，原链表变成1->1¢->2->2¢->3->3¢->null。
2．再从左到右遍历链表，在遍历时设置每一个副本节点的rand指针。还是举例来说明调整过程。
例如：此时链表为1->1¢->2->2¢->3->3¢->null，假设1的rand指针指向3，2的rand指针指向null，3的rand指针指向1。遍历到节点1时，节点1的下一个节点1.next就是其副本节点1¢。1的rand指针指向3，所以1¢的rand指针应该指向3¢。如何找到3¢呢？因为每个节点的副本节点都在自己的后一个，所以此时通过3.next就可以找到3¢，令1¢.next=3¢即可。以这种方式可以设置每一个副本节点的rand指针。
3．步骤2完成后，节点1，2，3，……之间的rand关系没有任何变化，节点1¢，2¢，3¢……之间的rand关系也被正确设置了，此时所有的节点与副本节点串在一起，将其分离出来即可。
例如：此时链表为1->1¢->2->2¢->3->3¢->null，分离成1->2->3->null和1¢->2¢->3¢->null即可，并且在这一步中，每个节点的rand指针不用做任何调整，在步骤2中都已经设置好。
4．将1¢节点作为结果返回即可。
进阶解法考查的依然是利用有限几个变量完成链表调整的代码实现能力。具体过程请参看如下代码中的copyListWithRand2方法。
public Node copyListWithRand2(Node head) {
if (head == null) {
return null;
}
Node cur = head;
Node next = null;
// 复制并链接每一个节点
while (cur != null) {
next = cur.next;
cur.next = new Node(cur.value);
cur.next.next = next;
cur = next;
}
cur = head;
Node curCopy = null;
// 设置复制节点的rand指针
while (cur != null) {
next = cur.next.next;
curCopy = cur.next;
curCopy.rand = cur.rand != null ? cur.rand.next : null;
cur = next;
}
Node res = head.next;
cur = head;
// 拆分
while (cur != null) {
next = cur.next.next;
curCopy = cur.next;
cur.next = next;
curCopy.next = next != null ? next.next : null;
cur = next;
}
return res;
}
两个单链表生成相加链表
【题目】
假设链表中每一个节点的值都在0～9之间，那么链表整体就可以代表一个整数。
例如：9->3->7，可以代表整数937。
给定两个这种链表的头节点head1和head2，请生成代表两个整数相加值的结果链表。
例如：链表1为9->3->7，链表2为6->3，最后生成新的结果链表为1->0->0->0。
【难度】
士 ★☆☆☆
【解答】
这道题难度较低，考查面试者基本的代码实现能力。一种实现方式是将两个链表先算出各自所代表的整数，然后求出两个整数的和，最后将这个和转换成链表的形式，但是这种方法有一个很大的问题，链表的长度可以很长，可以表达一个很大的整数。因此，转成系统中的int类型时可能会溢出，所以不推荐这种方法。
方法一：利用栈结构求解。
1．将两个链表分别从左到右遍历，遍历过程中将值压栈，这样就生成了两个链表节点值的逆序栈，分别表示为s1和s2。
例如：链表9->3->7，s1从栈顶到栈底为7，3，9；链表6->3，s2从栈顶到栈底为3，6。
2．将s1和s2同步弹出，这样就相当于两个链表从低位到高位依次弹出，在这个过程中生成相加链表即可，同时需要关注每一步是否有进位，用ca表示。
例如：s1先弹出7，s2先弹出3，这一步相加结果为10，产生了进位，令ca=1，然后生成一个节点值为0的新节点，记为new1；s1再弹出3，s2再弹出6，这时进位为ca=1，所以这一步相加结果为10，继续产生进位，仍令ca=1，然后生成一个节点值为0的新节点，记为new2，令new2.next=new1；s1再弹出9，s2为空，这时ca=1，这一步相加结果为10，仍令ca=1，然后生成一个节点值为0的新节点，记为new3，令new3.next=new2。这一步也是模拟简单的从低位到高位进位相加的过程。
3．当s1和s2都为空时，还要关注一下进位信息是否为1，如果为1，比如步骤2中的例子，表示还要生成一个节点值为1的新节点，记为new4，令new4.next=new3。
4．返回新生成的结果链表即可。
具体过程请参看如下代码中的addLists1方法。
public class Node {
public int value;
public Node next;
public Node(int data) {
this.value = data;
}
}
public Node addLists1(Node head1, Node head2) {
Stack<Integer> s1 = new Stack<Integer>();
Stack<Integer> s2 = new Stack<Integer>();
while (head1 != null) {
s1.push(head1.value);
head1 = head1.next;
}
while (head2 != null) {
s2.push(head2.value);
head2 = head2.next;
}
int ca = 0;
int n1 = 0;
int n2 = 0;
int n = 0;
Node node = null;
Node pre = null;
while (!s1.isEmpty() || !s2.isEmpty()) {
n1 = s1.isEmpty() ? 0 : s1.pop();
n2 = s2.isEmpty() ? 0 : s2.pop();
n = n1 + n2 + ca;
pre = node;
node = new Node(n % 10);
node.next = pre;
ca = n / 10;
}
if (ca == 1) {
pre = node;
node = new Node(1);
node.next = pre;
}
return node;
}
方法二：利用链表的逆序求解，可以节省用栈的空间。
1．将两个链表逆序，这样就可以依次得到从低位到高位的数字。
例如：链表9->3->7，逆序后变为7->3->9；链表6->3，逆序后变为3->6。
2．同步遍历两个逆序后的链表，这样就依次得到两个链表从低位到高位的数字，在这个过程中生成相加链表即可，同时需要关注每一步是否有进位，用ca表示。具体过程与方法一的步骤2相同。
3．当两个链表都遍历完成后，还要关注进位信息是否为1，如果为1，还要生成一个节点值为1的新节点。
4．将两个逆序的链表再逆序一次，即调整成原来的样子。
5．返回新生成的结果链表。
public Node addLists2(Node head1, Node head2) {
head1 = reverseList(head1);
head2 = reverseList(head2);
int ca = 0;
int n1 = 0;
int n2 = 0;
int n = 0;
Node c1 = head1;
Node c2 = head2;
Node node = null;
Node pre = null;
while (c1 != null || c2 != null) {
n1 = c1 != null ? c1.value : 0;
n2 = c2 != null ? c2.value : 0;
n = n1 + n2 + ca;
pre = node;
node = new Node(n % 10);
node.next = pre;
ca = n / 10;
c1 = c1 != null ? c1.next : null;
c2 = c2 != null ? c2.next : null;
}
if (ca == 1) {
pre = node;
node = new Node(1);
node.next = pre;
}
reverseList(head1);
reverseList(head2);
return node;
}
public Node reverseList(Node head) {
Node pre = null;
Node next = null;
while (head != null) {
next = head.next;
head.next = pre;
pre = head;
head = next;
}
return pre;
}
<p> 本专刊为左程云书《程序员代码面试指南》前三章，已获得官方授权，想看书中更多内容可去购买书籍查看。 同时点击可查看牛客算法笔面试真题精讲班，每周由左老师讲解经典高频校招题目：https://www.nowcoder.com/courses/cover/live/350 本专刊购买后即可解锁所有章节，故不可以退换哦~ </p> <p> <br /> </p>
