第二章：链表问题（五）
在单链表中删除指定值的节点
【题目】
给定一个链表的头节点head和一个整数num，请实现函数将值为num的节点全部删除。
例如，链表为1->2->3->4->null，num=3，链表调整后为：1->2->4->null。
【难度】
士 ★☆☆☆
【解答】
方法一：利用栈或者其他容器收集节点的方法。时间复杂度为O(N)，额外空间复杂度为O(N)。
将值不等于num的节点用栈收集起来，收集完成后重新连接即可。最后将栈底的节点作为新的头节点返回，具体过程请参看如下代码中的removeValue1方法。
public Node removeValue1(Node head, int num) {
Stack<Node> stack = new Stack<Node>();
while (head != null) {
if (head.value != num) {
stack.push(head);
}
head = head.next;
}
while (!stack.isEmpty()) {
stack.peek().next = head;
head = stack.pop();
}
return head;
} 方法二：不用任何容器而直接调整的方法。时间复杂度为O(N)，额外空间复杂度为O(1)。
首先从链表头开始，找到第一个值不等于num的节点，作为新的头节点，这个节点是肯定不用删除的，记为newHead。继续往后遍历，假设当前节点为cur，如果cur节点值等于num，就将cur节点删除，删除的方式是将之前最近一个值不等于num的节点pre连接到cur的下一个节点，即pre.next=cur.next；如果cur节点值不等于num，就令pre=cur，即更新最近一个值不等于num的节点。
具体实现过程请参看如下代码中的removeValue2方法。
public Node removeValue2(Node head, int num) {
while (head != null) {
if (head.value != num) {
break;
}
head = head.next;
}
Node pre = head;
Node cur = head;
while (cur != null) {
if (cur.value == num) {
pre.next = cur.next;
} else {
pre = cur;
}
cur = cur.next;
}
return head;
} 将搜索二叉树转换成双向链表
【题目】
对二叉树的节点来说，有本身的值域，有指向左孩子节点和右孩子节点的两个指针；对双向链表的节点来说，有本身的值域，有指向上一个节点和下一个节点的指针。在结构上，两种结构有相似性，现在有一棵搜索二叉树，请将其转换为一个有序的双向链表。
例如，节点定义为：
public class Node {
public int value;
public Node left;
public Node right;
public Node(int data) {
this.value = data;
}
} 一棵搜索二叉树如图2-11所示。
这棵搜索二叉树转换后的双向链表从头到尾依次是1～9。对每一个节点来说，原来的right指针等价于转换后的next指针，原来的left指针等价于转换后的last指针，最后返回转换后的双向链表头节点。
【难度】
尉 ★★☆☆
【解答】
方法一：用队列等容器收集二叉树中序遍历结果的方法。时间复杂度为O(N)，额外空间复杂度为O(N)，具体过程如下：
1．生成一个队列，记为queue，按照二叉树中序遍历的顺序，将每个节点放入queue中。
2．从queue中依次弹出节点，并按照弹出的顺序重连所有的节点即可。
方法一的具体实现请参看如下代码中的convert1方法。
public Node convert1(Node head) {
Queue<Node> queue = new LinkedList<Node>();
inOrderToQueue(head, queue);
if (queue.isEmpty()) {
return head;
}
head = queue.poll();
Node pre = head;
pre.left = null;
Node cur = null;
while (!queue.isEmpty()) {
cur = queue.poll();
pre.right = cur;
cur.left = pre;
pre = cur;
}
pre.right = null;
return head;
}
public void inOrderToQueue(Node head, Queue<Node> queue) {
if (head == null) {
return;
}
inOrderToQueue(head.left, queue);
queue.offer(head);
inOrderToQueue(head.right, queue);
} 方法二：利用递归函数，除此之外，不使用任何容器的方法。时间复杂度为O(N)，额外空间复杂度为O(h)，h为二叉树的高度。
实现递归函数process。process的输入参数是一棵二叉树的头节点X，功能是将以X为头的搜索二叉树转换为一个有序双向链表。返回值是这个有序双向链表的头节点和尾节点，所以返回值的类型是一个复杂结构，就是如下的RetrunType类。
public class RetrunType {
public Node start;
public Node end;
public RetrunType(Node start, Node end) {
this.start = start;
this.end = end;
}
} 具体过程为先把以X为头的搜索二叉树的左子树转换为有序双向链表，并且返回左子树有序双向链表的头和尾，然后把以X为头的搜索二叉树的右子树转换为有序双向链表，并且返回右子树有序双向链表的头和尾，接着通过X把两部分接起来即可。最后不要忘记，递归函数对任何节点的要求是一样的，所以要返回此时大的有序双向链表的头和尾。具体实现请参看如下代码中的convert2方法。
public Node convert2(Node head) {
if (head == null) {
return null;
}
return process(head).start;
}
public RetrunType process(Node head) {
if (head == null) {
return new RetrunType(null, null);
}
RetrunType leftList = process(head.left);
RetrunType rightList = process(head.right);
if (leftList.end != null) {
leftList.end.right = head;
}
head.left = leftList.end;
head.right = rightList.start;
if (rightList.start != null) {
rightList.start.left = head;
}
return new RetrunType(leftList.start != null ? leftList.start : head,
rightList.end != null ? rightList.end : head);
} 关于方法二中时间复杂度与空间复杂度的解释，可以用process递归函数发生的次数来估算时间复杂度，process会处理所有的子树，子树的数量就是二叉树节点的个数。所以时间复杂度为O(N)，process递归函数最多占用二叉树高度为h的栈空间，所以额外空间复杂度为O(h)。
【扩展】
本题在复杂度方面能够达到的程度完全取决于二叉树遍历的实现，如果一颗二叉树遍历的实现在时间和空间复杂度上足够好，那么本题在时间复杂度和空间复杂度上就同样好。有没有时间复杂度为O(N)、额外空间复杂度为O(1)的遍历实现呢？也就是既不用栈，也不用递归函数，只用有限几个变量的实现？有。有兴趣的读者可阅读本书“遍历二叉树的神级方法”问题，然后结合神级的遍历方法重新实现这道题。有关方法二中递归函数的设计方法，我们在本书的二叉树章节还能进一步学习并形成固定的套路。
单链表的选择排序
【题目】
给定一个无序单链表的头节点head，实现单链表的选择排序。
要求：额外空间复杂度为O(1)。
【难度】
士 ★☆☆☆
【解答】
既然要求额外空间复杂度为O(1)，就不能把链表装进数组等容器中进行排序，排好序之后再重新连接，而是要求面试者在原链表上利用有限几个变量完成选择排序的过程。选择排序是从未排序的部分中找到最小值，然后放在排好序部分的尾部，逐渐将未排序的部分缩小，最后全部变成排好序的部分。本书实现的方法模拟了这个过程。
1．开始时默认整个链表都是未排序的部分，对于找到的第一个最小值节点，肯定是整个链表的最小值节点，将其设置为新的头节点，记为newHead。
2．每次在未排序的部分中找到最小值的节点，然后把这个节点从未排序的链表中删除，删除的过程当然要保证未排序部分的链表在结构上不至于断开。例如，2->1->3，删除节点1之后，链表应该变成2->3，这就要求我们应该找到要删除节点的前一个节点。
3．把删除的节点（也就是每次的最小值节点）连接到排好序部分的链表尾部。
4．全部过程处理完后，整个链表都已经有序，返回newHead。
和选择排序一样，如果链表的长度为N，时间复杂度为O(N2)，额外空间复杂度为O(1)。
本题依然是考查调整链表的代码技巧，具体过程请参看如下代码中的selectionSort方法。
public static class Node {
public int value;
public Node next;
public Node(int data) {
this.value = data;
}
}
public static Node selectionSort(Node head) {
Node tail = null; // 排序部分尾部
Node cur = head; // 未排序部分头部
Node smallPre = null; // 最小节点的前一个节点
Node small = null; // 最小的节点
while (cur != null) {
small = cur;
smallPre = getSmallestPreNode(cur);
if (smallPre != null) {
small = smallPre.next;
smallPre.next = small.next;
}
cur = cur == small ? cur.next : cur;
if (tail == null) {
head = small;
} else {
tail.next = small;
}
tail = small;
}
return head;
}
public Node getSmallestPreNode(Node head) {
Node smallPre = null;
Node small = head;
Node pre = head;
Node cur = head.next;
while (cur != null) {
if (cur.value < small.value) {
smallPre = pre;
small = cur;
}
pre = cur;
cur = cur.next;
}
return smallPre;
} 一种怪异的节点删除方式
【题目】
链表节点值类型为int型，给定一个链表中的节点node，但不给定整个链表的头节点。如何在链表中删除node？请实现这个函数，并分析这样做会出现哪些问题。
要求：时间复杂度为O(1)。
【难度】
士 ★☆☆☆
【解答】
本题的思路很简单，举例就能说明具体的做法。
例如，链表1->2->3->null，只知道要删除节点2，而不知道头节点。那么只需把节点2的值变成节点3的值，然后在链表中删除节点3即可。
这道题目出现的次数很多，这么做看起来非常方便，但其实是有很大问题的。
问题一：这样的删除方式无法删除最后一个节点。还是以原示例来说明，如果知道要删除节点3，而不知道头节点。但它是最后的节点，根本没有下一个节点来代替节点3被删除，那么只有让节点2的next指向null这一种办法，而我们又根本找不到节点2，所以根本没法正确删除节点3。读者可能会问，我们能不能把节点3在内存上的区域变成null呢？这样不就相当于让节点2的next指针指向了null，起到节点3被删除的效果了吗？不可以。null在系统中是一个特定的区域，如果想让节点2的next指针指向null，必须找到节点2。
问题二：这种删除方式在本质上根本就不是删除了node节点，而是把node节点的值改变，然后删除node的下一个节点，在实际的工程中可能会带来很大问题。比如，工程上的一个节点可能代表很复杂的结构，节点值的复制会相当复杂，或者可能改变节点值这个操作都是被禁止的；再如，工程上的一个节点代表提供服务的一个服务器，外界对每个节点都有很多依赖，比如，示例中删除节点2时，其实影响了节点3对外提供的服务。
这种删除方式的具体过程请参看如下代码中的removeNodeWired方法。
public class Node {
public int value;
public Node next;
public Node(int data) {
this.value = data;
}
}
public void removeNodeWired(Node node) {
if (node == null) {
return;
}
Node next = node.next;
if (next == null) {
throw new RuntimeException("can not remove last node.");
}
node.value = next.value;
node.next = next.next;
} 向有序的环形单链表中插入新节点
【题目】
一个环形单链表从头节点head开始不降序，同时由最后的节点指回头节点。给定这样一个环形单链表的头节点head和一个整数num，请生成节点值为num的新节点，并插入到这个环形链表中，保证调整后的链表依然有序。
【难度】
士 ★☆☆☆
【解答】
直接给出时间复杂度为O(N)、额外空间复杂度为O(1)的方法。具体过程如下：
1．生成节点值为num的新节点，记为node。
2．如果链表为空，让node自己组成环形链表，然后直接返回node。
3．如果链表不为空，令变量pre=head，cur=head.next，然后令pre和cur同步移动下去，如果遇到pre的节点值小于或等于num，并且cur的节点值大于或等于num，说明node应该在pre节点和cur节点之间插入，插入node，然后返回head即可。例如，链表1->3->4->1->…，num=2。应该把节点值为2的节点插入到1和3之间，然后返回头节点。
4．如果pre和cur转了一圈，这期间都没有发现步骤3所说的情况，说明node应该插入到头节点的前面，这种情况之所以会发生，要么是因为node节点的值比链表中每个节点的值都大，要么是因为node的值比链表中每个节点的值都小。
分别举两个例子：示例1，链表1->3->4->1->…，num=5，应该把节点值为5的节点插入到节点1的前面；示例2，链表1->3->4->1->…，num=0，也应该把节点值为0的节点插入到节点1的前面。
5．如果node节点的值比链表中每个节点的值都大，返回原来的头节点即可；如果node节点的值比链表中每个节点的值都小，应该把node作为链表新的头节点返回。
具体过程请参看如下代码中的insertNum方法。
public class Node {
public int value;
public Node next;
public Node(int data) {
this.value = data;
}
}
public Node insertNum(Node head, int num) {
Node node = new Node(num);
if (head == null) {
node.next = node;
return node;
}
Node pre = head;
Node cur = head.next;
while (cur != head) {
if (pre.value <= num && cur.value >= num) {
break;
}
pre = cur;
cur = cur.next;
}
pre.next = node;
node.next = cur;
return head.value < num ? head : node;
} 合并两个有序的单链表
【题目】
给定两个有序单链表的头节点head1和head2，请合并两个有序链表，合并后的链表依然有序，并返回合并后链表的头节点。
例如：
0->2->3->7->null
1->3->5->7->9->null
合并后的链表为：0->1->2->3->3->5->7->7->9->null
【难度】
士 ★☆☆☆
【解答】
本题比较简单，假设两个链表的长度分别为M和N，直接给出时间复杂度为O(M+N)、额外空间复杂度为O(1)的方法。具体过程如下：
1．如果两个链表中有一个为空，说明无须合并过程，返回另一个链表的头节点即可。
2．比较head1和head2的值，小的节点也是合并后链表的最小节点，这个节点无疑应该是合并链表的头节点，记为head；在之后的步骤里，哪个链表的头节点的值更小，另一个链表的所有节点都会依次插入到这个链表中。
3．不妨设head节点所在的链表为链表1，另一个链表为链表2。链表1和链表2都从头部开始一起遍历，比较每次遍历到的两个节点的值，记为cur1和cur2，然后根据大小关系做出不同的调整，同时用一个变量pre表示上次比较时值较小的节点。
例如，链表1为1->5->6->null，链表2为2->3->7->null。
cur1=1，cur2=2，pre=null。cur1小于cur2，不做调整，因为此时cur1较小，所以令pre=cur1=1，然后继续遍历链表1的下一个节点，也就是节点5。
cur1=5，cur2=2，pre=1。cur2小于cur1，让pre的next指针指向cur2，cur2的next指针指向cur1，这样，cur2便插入到链表1中。因为此时cur2较小，所以令pre=cur2=2，然后继续遍历链表2的下一个节点，也就是节点3。这一步完成后，链表1变为1->2->5->6->null，链表2变为3->7->null，cur1=5，cur2=3，pre=2。
cur1=5，cur2=3，pre=2。此时又是cur2较小，与上一步调整类似，这一步完成后，链表1变为1->2->3->5->6->null，链表2为7->null，cur1=5，cur2=7，pre=3。
cur1=5，cur2=7，pre=3。cur1小于cur2，不做调整，因为此时cur1较小，所以令pre=cur1=5，然后继续遍历链表1的下一个节点，也就是节点6。
cur1=6，cur2=7，pre=5。cur1小于cur2，不做调整，因为此时cur1较小，所以令pre=cur1=6，此时已经走到链表1的最后一个节点，再往下就结束，如果链表1或链表2有任何一个走到了结束，就进入步骤4。
4．如果链表1先走完，此时cur1=null，pre为链表1的最后一个节点，那么就把pre的next指针指向链表2当前的节点（即cur2），表示把链表2没遍历到的有序部分直接拼接到最后，调整结束。如果链表2先走完，说明链表2的所有节点都已经插入到链表1中，调整结束。
5．返回合并后链表的头节点head。
全部过程请参看如下代码中的merge方法。
public class Node {
public int value;
public Node next;
public Node(int data) {
this.value = data;
}
}
public Node merge(Node head1, Node head2) {
if (head1 == null || head2 == null) {
return head1 != null ? head1 : head2;
}
Node head = head1.value < head2.value ? head1 : head2;
Node cur1 = head == head1 ? head1 : head2;
Node cur2 = head == head1 ? head2 : head1;
Node pre = null;
Node next = null;
while (cur1 != null && cur2 != null) {
if (cur1.value <= cur2.value) {
pre = cur1;
cur1 = cur1.next;
} else {
next = cur2.next;
pre.next = cur2;
cur2.next = cur1;
pre = cur2;
cur2 = next;
}
}
pre.next = cur1 == null ? cur2 : cur1;
return head;
}
按照左右半区的方式重新组合单链表
【题目】
给定一个单链表的头部节点head，链表长度为N，如果N为偶数，那么前N/2个节点算作左半区，后N/2个节点算作右半区；如果N为奇数，那么前N/2个节点算作左半区，后N/2+1个节点算作右半区。左半区从左到右依次记为L1->L2->…，右半区从左到右依次记为R1->R2->…，请将单链表调整成L1->R1->L2->R2->…的形式。
例如：
1->null，调整为1->null。
1->2->null，调整为1->2->null。
1->2->3->null，调整为1->2->3->null。
1->2->3->4->null，调整为1->3->2->4->null。
1->2->3->4->5->null，调整为1->3->2->4->5->null。
1->2->3->4->5->6->null，调整为1->4->2->5->3->6->null。
【难度】
士 ★☆☆☆
【解答】
假设链表的长度为N，直接给出时间复杂度为O(N)、额外空间复杂度为O(1)的方法。具体过程如下：
1．如果链表为空或长度为1，不用调整，过程直接结束。
2．链表长度大于1时，遍历一遍找到左半区的最后一个节点，记为mid。
例如：1->2，mid为1；1->2->3，mid为1；1->2->3->4，mid为2；1->2->3->4->5，mid为2；1->2->3->4->5->6，mid为3。也就是说，从长度为2开始，长度每增加2，mid就往后移动一个节点。
3．遍历一遍找到mid之后，将左半区与右半区分离成两个链表（mid.next=null），分别记为left(head)和right（原来的mid.next）。
4．将两个链表按照题目要求合并起来。
具体过程请参看如下代码中的relocate方法，其中的mergeLR方法为步骤4的合并过程。
public class Node {
public int value;
public Node next;
public Node(int value) {
this.value = value;
}
}
public void relocate(Node head) {
if (head == null || head.next == null) {
return;
}
Node mid = head;
Node right = head.next;
while (right.next != null && right.next.next != null) {
mid = mid.next;
right = right.next.next;
}
right = mid.next;
mid.next = null;
mergeLR(head, right);
}
public void mergeLR(Node left, Node right) {
Node next = null;
while (left.next != null) {
next = right.next;
right.next = left.next;
left.next = right;
left = right.next;
right = next;
}
left.next = right;
}
<p> 本专刊为左程云书《程序员代码面试指南》前三章，已获得官方授权，想看书中更多内容可去购买书籍查看。 同时点击可查看牛客算法笔面试真题精讲班，每周由左老师讲解经典高频校招题目：https://www.nowcoder.com/courses/cover/live/350 本专刊购买后即可解锁所有章节，故不可以退换哦~ </p> <p> <br /> </p>
投递阿里云等公司10个岗位 >
