第二章：链表问题（一）
打印两个有序链表的公共部分
【题目】
给定两个有序链表的头指针head1和head2，打印两个链表的公共部分。
【难度】
士 ★☆☆☆
【解答】
本题难度很低，因为是有序链表，所以从两个链表的头开始进行如下判断：
— 如果head1的值小于head2，则head1往下移动。
— 如果head2的值小于head1，则head2往下移动。
— 如果head1的值与head2的值相等，则打印这个值，然后head1与head2都往下移动。
— head1或head2有任何一个移动到null，则整个过程停止。
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变化为：3 2 1
链表：1->2->3，K = 3，链表倒数第3个节点是1节点。
走到的节点：1 -> 2 -> 3
K变化为：2 1 0
链表：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的目的。
如果K值小于0，如何找到要删除节点的前一个节点呢？方法如下：
1．重新从头节点开始走，每移动一步，就让K的值加1。
2．当K等于0时，移动停止，移动到的节点就是要删除节点的前一个节点。
这样做是非常好理解的，因为如果链表长度为N，要删除倒数第K个节点，很明显，倒数第K个节点的前一个节点就是第N-K个节点。在第一次遍历后，K的值变为K-N。第二次遍历时，K的值不断加1，加到0就停止遍历，第二次遍历当然会停到第N-K个节点的位置。
public class Node {
public int value;
public Node next;
public Node(int data) {
this.value = data;
}
}
public Node removeLastKthNode(Node head, int lastKth) {
if (head == null || lastKth < 1) {
return head;
}
Node cur = head;
while (cur != null) {
lastKth--;
cur = cur.next;
}
if (lastKth == 0) {
head = head.next;
}
if (lastKth < 0) {
cur = head;
while (++lastKth != 0) {
cur = cur.next;
}
cur.next = cur.next.next;
}
return head;
}
public class DoubleNode {
public int value;
public DoubleNode last;
public DoubleNode next;
public DoubleNode(int data) {
this.value = data;
}
}
public DoubleNode removeLastKthNode(DoubleNode head, int lastKth) {
if (head == null || lastKth < 1) {
return head;
}
DoubleNode cur = head;
while (cur != null) {
lastKth--;
cur = cur.next;
}
if (lastKth == 0) {
head = head.next;
head.last = null;
}
if (lastKth < 0) {
cur = head;
while (++lastKth != 0) {
cur = cur.next;
}
DoubleNode newNext = cur.next.next;
cur.next = newNext;
if (newNext != null) {
newNext.last = cur;
}
}
return head;
}
删除链表的中间节点和a/b处的节点
【题目】
给定链表的头节点head，实现删除链表的中间节点的函数。
例如：
不删除任何节点；
1->2，删除节点1；
1->2->3，删除节点2；
1->2->3->4，删除节点2；
1->2->3->4->5，删除节点3；
进阶：
给定链表的头节点head、整数a和b，实现删除位于a/b处节点的函数。
例如：
链表：1->2->3->4->5，假设a/b的值为r。
如果r等于0，不删除任何节点；
如果r在区间(0, 1/5]上，删除节点1；
如果r在区间(1/5, 2/5]上，删除节点2；
如果r在区间(2/5, 3/5]上，删除节点3；
如果r在区间(3/5, 4/5]上，删除节点4；
如果r在区间(4/5, 1]上，删除节点5；
如果r大于1，不删除任何节点。
【难度】
士 ★☆☆☆
【解答】
先来分析原问题，如果链表为空或者长度为1，不需要调整，则直接返回；如果链表的长度为2，将头节点删除即可；当链表长度到达3，应该删除第2个节点；当链表长度为4，应该删除第2个节点；当链表长度为5，应该删除第3个节点……也就是链表长度每增加2（3,5,7…），要删除的节点就后移一个节点。删除节点的问题在之前的题目中我们已经讨论过，如果要删除一个节点，则需要找到待删除节点的前一个节点。
public class Node {
public int value;
public Node next;
public Node(int data) {
this.value = data;
}
}
public Node removeMidNode(Node head) {
if (head == null || head.next == null) {
return head;
}
if (head.next.next == null) {
return head.next;
}
Node pre = head;
Node cur = head.next.next;
while (cur.next != null && cur.next.next != null) {
pre = pre.next;
cur = cur.next.next;
}
pre.next = pre.next.next;
return head;
}
接下来讨论进阶问题，首先需要解决的问题是，如何根据链表的长度n，以及a与b的值决定该删除的节点是哪一个节点呢？根据如下方法：先计算double r = ((double) (a * n)) / ((double) b)的值，然后r向上取整之后的整数值代表该删除的节点是第几个节点。
下面举几个例子来验证一下。
如果链表长度为7，a=5，b=7。
r = (7*5)/7 = 5.0，向上取整后为5，所以应该删除第5个节点。
如果链表长度为7，a=5，b=6。
r = (7*5)/6 = 5.8333…，向上取整后为6，所以应该删除第6个节点。
如果链表长度为7，a=1，b=6。
r = (7*1)/6 = 1.1666…，向上取整后为2，所以应该删除第2个节点。
public Node removeByRatio(Node head, int a, int b) {
if (a < 1 || a > b) {
return head;
}
int n = 0;
Node cur = head;
while (cur != null) {
n++;
cur = cur.next;
}
n = (int) Math.ceil(((double) (a * n)) / (double) b);
if (n == 1) {
head = head.next;
}
if (n > 1) {
cur = head;
while (--n != 1) {
cur = cur.next;
}
cur.next = cur.next.next;
}
return head;
}
反转单向和双向链表
【题目】
分别实现反转单向链表和反转双向链表的函数。
【要求】
如果链表长度为N，时间复杂度要求为O(N)，额外空间复杂度要求为O(1)。
【难度】
士 ★☆☆☆
【解答】
本题比较简单，读者做到代码一次完成，运行不出错即可。
public class Node {
public int value;
public Node next;
public Node(int data) {
this.value = data;
}
}
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;
} public DoubleNode {
public int value;
public DoubleNode last;
public DoubleNode next;
public DoubleNode(int data) {
this.value = data;
}
}
public DoubleNode reverseList(DoubleNode head) {
DoubleNode pre = null;
DoubleNode next = null;
while (head != null) {
next = head.next;
head.next = pre;
head.last = next;
pre = head;
head = next;
}
return pre;
}
反转部分单向链表
【题目】
给定一个单向链表的头节点head，以及两个整数from和to，在单向链表上把第from个节点到第to个节点这一部分进行反转。
例如：
1->2->3->4->5->null，from=2，to=4
调整结果为：1->4->3->2->5->null
再如：
1->2->3->null，from=1，to=3
调整结果为：3->2->1->null
【要求】
1．如果链表长度为N，时间复杂度要求为O(N)，额外空间复杂度要求为O(1)。
2．如果不满足1<=from<=to<=N，则不用调整。
【难度】
士 ★☆☆☆
【解答】
本题有可能存在换头的问题，比如题目的第二个例子，所以函数应该返回调整后的新头节点，整个处理过程如下：
1．先判断是否满足1≤from≤to≤N，如果不满足，则直接返回原来的头节点。
2．找到第from-1个节点fPre和第to+1个节点tPos。fPre就是要反转部分的前一个节点，tPos是反转部分的后一个节点。把反转的部分先反转，然后正确地连接fPre和tPos。
例如：1->2->3->4->null，假设fPre为节点1，tPos为节点4，要反转部分为2->3。先反转成3->2，然后fPre连向节点3，节点2连向tPos，就变成了1->3->2->4->null。
3．如果fPre为null，说明反转部分是包含头节点的，则返回新的头节点，也就是没反转之前反转部分的最后一个节点，也是反转之后反转部分的第一个节点；如果fPre不为null，则返回旧的头节点。
public Node reversePart(Node head, int from, int to) {
int len = 0;
Node node1 = head;
Node fPre = null;
Node tPos = null;
while (node1 != null) {
len++;
fPre = len == from - 1 ? node1 : fPre;
tPos = len == to + 1 ? node1 : tPos;
node1 = node1.next;
}
if (from > to || from < 1 || to > len) {
return head;
}
node1 = fPre == null ? head : fPre.next;
Node node2 = node1.next;
node1.next = tPos;
Node next = null;
while (node2 != tPos) {
next = node2.next;
node2.next = node1;
node1 = node2;
node2 = next;
}
if (fPre != null) {
fPre.next = node1;
return head;
}
return node1;
}
<p> 本专刊为左程云书《程序员代码面试指南》前三章，已获得官方授权，想看书中更多内容可去购买书籍查看。 同时点击可查看牛客算法笔面试真题精讲班，每周由左老师讲解经典高频校招题目：https://www.nowcoder.com/courses/cover/live/350 本专刊购买后即可解锁所有章节，故不可以退换哦~ </p> <p> <br /> </p>
一汽大众公司氛围 7人发布
