本篇文章是上篇文章的一个补充数据结构之表的总结
合并两个排序的链表
题目：输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序。
链表1: 1 --> 3 --> 5 --> 7
链表2: 2 --> 4 --> 6 --> 8
合并之后的链表： 1-->2-->3-->4-->5-->6-->7-->8
如上所示，首先我们需要分析链表合并的过程：
首先我们从两个链表的头节点开始分析，链表1的头节点小于链表2的头节点，那么链表1的头节点就是合并链表的头节点。然后再用链表1头节点的下一个节点N和链表2的头节点对比，如果链表1的N节点还是小于链表2的头节点，那么，N节点就作为合并链表的下一个节点，然后N节点的下一个节点继续和链表2的头节点对比。如果链表1N节点大于链表2的头节点，那么链表2的头节点作为合并链表的下一个节点，然后链表2的头节点的下一个节点M 和 链表1的N节点继续对比，如此得到一个递增排序的新的链表，很明显这是一个典型的递归的过程。
如果你还感觉有点懵懵的，我用下面来这样表示就清楚了。
P1(表示第一个链表)
1 --> 3 --> 5 --> 7
P2(表示第二个链表)
2 --> 4 --> 6 --> 8
3 5 7
1
2 4 6 8
3 5 7
1-->2
4 6 8
5 7
1-->2-->3
4 6 8
......
分析完合并过程后，我们还需要来解决鲁棒性的问题。比如空链表的问题，如果第一个链表是空链表而第二个链表不是空链表，那么合并后的新链表就是第二个链表。反之是第一个链表。如果两个链表都为空那么，合并的链表就是空链表。
ok,想清楚合并链表的分析过程和代码的鲁棒性，就可以动手写代码了。
public Node mergeInt(Node pHead1, Node pHead2) {
if (pHead1 == null) {
return pHead2;
} else if (pHead2 == null) {
return pHead1;
}
Node mergeHead = null;
Integer date1 = (Integer) pHead1.date;
Integer date2 = (Integer) pHead2.date;
if (date1 < date2) {
mergeHead = pHead1;
mergeHead.next = mergeInt(pHead1.next, pHead2);
} else {
mergeHead = pHead2;
mergeHead.next = mergeInt(pHead1, pHead2.next);
}
return mergeHead;
}
这道题考验了分析问题的能力和代码的鲁棒性。
链表中倒数第k个节点
题目：输出链表倒数第K个节点，且只能遍历链表一次。
当我们看到这个题目的时候得到倒数第k个节点，很自然的就会想到先走到链表的尾端，再从尾端回回朔k步，很简单就能得到。可是本题的链表是单链表，而单链表的节点只有从前往后没有从后往前，这种思路也只能pass掉。
既然不能从尾节点开始遍历，那么我们将思路回到头节点上来。假设整个链表有n个节点，那么倒数第k个节点从头开始数 就是 n-k+1节点。首先我们要得到链表中节点的个数n,然后从头节点走 n-k+1 个就行了。但是这要我们就需要遍历两次链表，题目要求只能遍历一次链表。
从上面的分析来看，我们的思路是正确的，但是如何实现一次遍历呢？我们可以定义两个指针，第一个指针从头节点开始遍历向前走k-1步，第二个指针保持不动。从第k步开始，第二个指针从头节点开始遍历，两个指针正好相差k-1步，当第一个指针到达尾节点时，第二个指针正好指向倒数第k个节点。
OK，分析了这么多，我们终于找到了解决办法，那么就可以很快写出下面的代码：
public Node findKthToTail(Node pHead, int k) {
Node pA = pHead;
Node pB = null;
for (int i = 0; i < k - 1; i++) {
pA = pA.next;
}
pB = pHead;
while (pA.next != null) {
pA = pA.next;
pB = pB.next;
}
return pB;
}
如果你真的是上面这样写的，那么你会被直接pass掉。Why？
上面的那段代码，没有考虑到代码的鲁棒性。
什么是鲁棒性呢？
所谓的鲁棒性就是指程序能够判断输入是否呵护规范要求，并对不符合要求的输入予以合理的处理。
有三种办法可以让上述代码崩溃：
- pHead = null
- 链表的总数小于k
- k = 0
这样潜在风险的代码，相信如果你是面试官，你也不会录用的。
修改之后的代码：
public Node findKthToReal(Node pHead, int k) {
if (pHead == null || k == 0) {
return null;
}
Node pA = pHead;
Node pB = null;
for (int i = 0; i < k - 1; i++) {
if (pA.next != null) {
pA = pA.next;
} else {
return null;
}
}
pB = pHead;
while (pA.next != null) {
pA = pA.next;
pB = pB.next;
}
return pB;
}
举一反三：
当我们用一个指针遍历链表不能解决问题时，可以尝试用两个指针来遍历链表。可以让其中一个指针遍历的速度更快一些（比如一次在链表上走两步），或者让它先在链表上走若干步。
这道题考验了我们解决问题的思路和代码的鲁棒性。
链表的中间节点,且只能遍历链表一次
如果懂了上面一道题，那么这道题也很简单。是上面那道题的扩展题。
分析：当看到一道题目时，不要着急写代码，先要分析以下。如果链表的总数为奇数则返回中间的节点，如果链表的总数为偶数，则返回中间两个节点的任意一个。定义两个指针，同时从链表的头节点出发，一个指针一次走一步，另一个指针一次走两步，当走的快的指针走到链表尾部时，走的慢的指针正好走到了中间节点。
鲁棒性：1. 头节点不能为空。2. 走的快的指针不能为空。
我们很快就能写出代码：
public Node findMid(Node pHead) {
if (pHead == null) {
return null;
}
Node pA = pHead;
Node pB = pHead;
while (pA.next != null) {
if (pA.next.next != null) {
pA = pA.next.next;
pB = pB.next;
} else {
pA = pA.next;
//可以取前一个或者后一个
pB = pB.next;
}
}
return pB;
}
链表中环的入口节点
带中环的链表
如上图所示，
要想解决这个问题：
-
第一步如何确定一个链表中包含环。
这个问题我们依然可以用两个指针来解决问题，两个指针同时从链表的头节点出发，一个指针一次走一步，另一个指针一次走两步。如果走的快的指针追上了走的慢的指针，那么链表就包含环。如果走的快的指针走到链表的末尾(pNode.next == null),那么链表就不包含环，如果你弄懂上述问题，这一步相信你可以很快写出代码。
-
第二步如何得到环中节点的个数。
从第一步中可以看出，如果两个指针相遇，那么就一定存在环，且两个指针相遇的节点一定在环中，从这个节点出发，一边移动一边计数，再次回到这个节点，就可以得到环中节点个数了。 -
第三部如何找到环的入口。
image.png
这一步还是用两个指针来解决问题，P1和P2两个指针指向头节点，P1线在链表上向前移动n(n 就是中环节点的个数也就是第二步得到的个数)步，然后两个指针以相同速度向前移动，它们相遇的节点就是中环的入口节点。
具体实现代码如下：
/**
* 找到两个指针相遇的节点
*
* @param pHead
* @return
*/
public Node findMettingNode(Node pHead) {
if (pHead == null) {
return null;
}
Node pSolw = pHead.next;
if (pSolw == null) {
return null;
}
Node pFast = pSolw.next;
if (pFast == null) {
return null;
}
while (pFast != null && pSolw != null) {
if (pFast == pSolw) {
return pFast;
}
pSolw = pSolw.next;
pFast = pFast.next;
if (pFast != null) {
pFast = pFast.next;
}
}
return null;
}
/**
* 判断是否存在环，然后计算环的节点个数，最后得到环的入口
*
* @param pHead
* @return
*/
public Node entryNode(Node pHead) {
Node mettingNode = findMettingNode(pHead);
if (mettingNode == null) {
return null;
}
//得到中环节点的数目
int size = 1;
Node mettingNode1 = mettingNode;
while (mettingNode1.next != mettingNode) {
++size;
mettingNode1 = mettingNode1.next;
}
//先移动中环节点的次数
mettingNode1 = pHead;
for (int i = 0; i < size; i++) {
mettingNode1 = mettingNode1.next;
}
//在移动 1 和 2
Node mettingNode2 = pHead;
while (mettingNode1 != mettingNode2) {
mettingNode1 = mettingNode1.next;
mettingNode2 = mettingNode2.next;
}
return mettingNode1;
}
网友评论