第二章：链表问题（四）
两个单链表相交的一系列问题
【题目】
在本题中，单链表可能有环，也可能无环。给定两个单链表的头节点head1和head2，这两个链表可能相交，也可能不相交。请实现一个函数，如果两个链表相交，请返回相交的第一个节点；如果不相交，返回null即可。
要求：如果链表1的长度为N，链表2的长度为M，时间复杂度请达到O(N+M)，额外空间复杂度请达到O(1)。
【难度】
将 ★★★★
【解答】
这道题需要分析的情况非常多，同时因为有额外空间复杂度为O(1)的限制，所以实现起来也比较困难。
本题可以拆分成三个子问题，每个问题都可以作为一道独立的算法题，具体如下。
问题一：如何判断一个链表是否有环，如果有，则返回第一个进入环的节点，没有则返回null。
问题二：如何判断两个无环链表是否相交，相交则返回第一个相交节点，不相交则返回null。
问题三：如何判断两个有环链表是否相交，相交则返回第一个相交节点，不相交则返回null。
注意：如果一个链表有环，另外一个链表无环，它们是不可能相交的，直接返回null。
下面逐一分析每个问题。
问题一：如何判断一个链表是否有环，如果有，则返回第一个进入环的节点，没有则返回null。
如果一个链表没有环，那么遍历链表一定可以遇到链表的终点；如果链表有环，那么遍历链表就永远在环里转下去了。如何找到第一个入环节点，具体过程如下：
1．设置一个慢指针slow和一个快指针fast。在开始时，slow和fast都指向链表的头节点head。然后slow每次移动一步，fast每次移动两步，在链表中遍历起来。
2．如果链表无环，那么fast指针在移动过程中一定先遇到终点，一旦fast到达终点，说明链表是没有环的，直接返回null，表示该链表无环，当然也没有第一个入环的节点。
3．如果链表有环，那么fast指针和slow指针一定会在环中的某个位置相遇，当fast和slow相遇时，fast指针重新回到head的位置，slow指针不动。接下来，fast指针从每次移动两步改为每次移动一步，slow指针依然每次移动一步，然后继续遍历。
4．fast指针和slow指针一定会再次相遇，并且在第一个入环的节点处相遇。证明略。
注意：你也可以用哈希表完成问题一的判断，但是不符合题目关于空间复杂度的要求。
问题一的具体实现请参看如下代码中的getLoopNode方法。
public Node getLoopNode(Node head) {
if (head == null || head.next == null || head.next.next == null) {
return null;
}
Node n1 = head.next; // n1 -> slow
Node n2 = head.next.next; // n2 -> fast
while (n1 != n2) {
if (n2.next == null || n2.next.next == null) {
return null;
}
n2 = n2.next.next;
n1 = n1.next;
}
n2 = head; // n2 -> walk again from head
while (n1 != n2) {
n1 = n1.next;
n2 = n2.next;
}
return n1;
} 如果解决了问题一，我们就知道了两个链表有环或者无环的情况。如果一个链表有环，另一个链表无环，那么这两个链表是无论如何也不可能相交的。能相交的情况就分为两种，一种是两个链表都无环，即问题二；另一种是两个链表都有环，即问题三。
问题二：如何判断两个无环链表是否相交，相交则返回第一个相交节点，不相交则返回null。
如果两个无环链表相交，那么从相交节点开始，一直到两个链表终止的这一段，是两个链表共享的。解决问题二的具体过程如下：
1．链表1从头节点开始，走到最后一个节点（不是结束），统计链表1的长度记为len1，同时记录链表1的最后一个节点记为end1。
2．链表2从头节点开始，走到最后一个节点（不是结束），统计链表2的长度记为len2，同时记录链表2的最后一个节点记为end2。
3．如果end1!=end2，说明两个链表不相交，返回null即可；如果end==end2，说明两个链表相交，进入步骤4来找寻第一个相交节点。
4．如果链表1比较长，链表1就先走len1-len2步；如果链表2比较长，链表2就先走len2-len1步。然后两个链表一起走，一起走的过程中，两个链表第一次走到一起的那个节点就是第一个相交的节点。
例如：链表1长度为100，链表2长度为30，如果已经由步骤3确定了链表1和链表2一定相交，那么接下来，链表1先走70步，然后链表1和链表2一起走，它们一定会共同进入第一个相交的节点。
问题二的具体实现请参看如下代码中的noLoop方法。
public Node noLoop(Node head1, Node head2) {
if (head1 == null || head2 == null) {
return null;
}
Node cur1 = head1;
Node cur2 = head2;
int n = 0;
while (cur1.next != null) {
n++;
cur1 = cur1.next;
}
while (cur2.next != null) {
n--;
cur2 = cur2.next;
}
if (cur1 != cur2) {
return null;
}
cur1 = n > 0 ? head1 : head2;
cur2 = cur1 == head1 ? head2 : head1;
n = Math.abs(n);
while (n != 0) {
n--;
cur1 = cur1.next;
}
while (cur1 != cur2) {
cur1 = cur1.next;
cur2 = cur2.next;
}
return cur1;
} 问题三：如何判断两个有环链表是否相交，相交则返回第一个相交节点，不相交则返回null。
考虑问题三的时候，我们已经得到了两个链表各自的第一个入环节点，假设链表 1 的第一个入环节点记为loop1，链表2的第一个入环节点记为loop2。以下是解决问题三的过程。
1．如果loop1==loop2，那么两个链表的拓扑结构如图2-8所示。
这种情况下，我们只要考虑链表1从头开始到loop1这一段与链表2从头开始到loop2这一段，在那里第一次相交即可，而不用考虑进环该怎么处理，这就与问题二类似，只不过问题二是把null作为一个链表的终点，而这里是把loop1(loop2)作为链表的终点。但是判断的主要过程是相同的。
2．如果loop1!=loop2，两个链表不相交的拓扑结构如图2-9所示。两个链表相交的拓扑结构如图2-10所示。
如何分辨是这两种拓扑结构的哪一种呢？进入步骤3。
3．让链表1从loop1出发，因为loop1和之后的所有节点都在环上，所以将来一定能回到loop1。如果回到loop1之前并没有遇到loop2，说明两个链表的拓扑结构如图2-9所示，也就是不相交，直接返回null；如果回到loop1之前遇到了loop2，说明两个链表的拓扑结构如图2-10所示，也就是相交。因为loop1和loop2都在两条链表上，只不过loop1是离链表1较近的节点，loop2是离链表2较近的节点。所以，此时返回loop1或loop2都可以。
问题三的具体实现参看如下代码中的bothLoop方法。
public Node bothLoop(Node head1, Node loop1, Node head2, Node loop2) {
Node cur1 = null;
Node cur2 = null;
if (loop1 == loop2) {
cur1 = head1;
cur2 = head2;
int n = 0;
while (cur1 != loop1) {
n++;
cur1 = cur1.next;
}
while (cur2 != loop2) {
n--;
cur2 = cur2.next;
}
cur1 = n > 0 ? head1 : head2;
cur2 = cur1 == head1 ? head2 : head1;
n = Math.abs(n);
while (n != 0) {
n--;
cur1 = cur1.next;
}
while (cur1 != cur2) {
cur1 = cur1.next;
cur2 = cur2.next;
}
return cur1;
} else {
cur1 = loop1.next;
while (cur1 != loop1) {
if (cur1 == loop2) {
return loop1;
}
cur1 = cur1.next;
}
return null;
}
} 全部过程参看如下代码中的getIntersectNode方法，这也是整个题目的主方法。
public class Node {
public int value;
public Node next;
public Node(int data) {
this.value = data;
}
}
public Node getIntersectNode(Node head1, Node head2) {
if (head1 == null || head2 == null) {
return null;
}
Node loop1 = getLoopNode(head1);
Node loop2 = getLoopNode(head2);
if (loop1 == null && loop2 == null) {
return noLoop(head1, head2);
}
if (loop1 != null && loop2 != null) {
return bothLoop(head1, loop1, head2, loop2);
}
return null;
} 将单链表的每K个节点之间逆序
【题目】
给定一个单链表的头节点head，实现一个调整单链表的函数，使得每K个节点之间逆序，如果最后不够K个节点一组，则不调整最后几个节点。
例如：
链表：1->2->3->4->5->6->7->8->null，K=3。
调整后为：3->2->1->6->5->4->7->8->null。其中7、8不调整，因为不够一组。
【难度】
尉 ★★☆☆
【解答】
首先，如果K的值小于2，不用进行任何调整。因为K<1没有意义，K==1时，代表每1个节点为1组进行逆序，原链表也没有任何变化。接下来介绍两种方法，如果链表长度为N，方法一的时间复杂度为O(N)，额外空间复杂度为O(K)。方法二的时间复杂度为O(N)，额外空间复杂度为O(1)。本题考查面试者代码实现不出错的能力。
方法一：利用栈结构的解法。
1．从左到右遍历链表，如果栈的大小不等于K，就将节点不断压入栈中。
2．当栈的大小第一次到达K时，说明第一次凑齐了K个节点进行逆序，从栈中依次弹出这些节点，并根据弹出的顺序重新连接，这一组逆序完成后，需要记录一下新的头部，同时第一组的最后一个节点（原来是头节点）应该连接下一个节点。
例如：链表1->2->3->4->5->6->7->8->null，K = 3。第一组节点进入栈，从栈顶到栈底依次为3，2，1。逆序重连之后为3->2->1->…，然后节点1去连接节点4，链表变为3->2->1->4->5->6->7->8->null，之后从节点4开始不断处理K个节点为一组的后续情况，也就是步骤3，并且需要记录节点3，因为链表的头部已经改变，整个过程结束后需要返回这个新的头节点，记为newHead。
3．步骤2之后，当栈的大小每次到达K时，说明又凑齐了一组应该进行逆序的节点，从栈中依次弹出这些节点，并根据弹出的顺序重新连接。这一组逆序完成后，该组的第一个节点（原来是该组最后一个节点）应该被上一组的最后一个节点连接上，这一组的最后一个节点（原来是该组第一个节点）应该连接下一个节点。然后继续去凑下一组，直到链表都被遍历完。
例如：链表3->2->1->4->5->6->7->8->null，K = 3，第一组已经处理完。第二组从栈顶到栈底依次为6，5，4。逆序重连之后为6->5->4，然后节点6应该被节点1连接，节点4应该连接节点7，链表变为3->2->1->6->5->4->7->8->null。然后继续从节点7往下遍历。
4．最后应该返回newHead，作为链表新的头节点。
方法一的具体实现请参看如下代码中的reverseKNodes1方法。
public class Node {
public int value;
public Node next;
public Node(int data) {
this.value = data;
}
}
public Node reverseKNodes1(Node head, int K) {
if (K < 2) {
return head;
}
Stack<Node> stack = new Stack<Node>();
Node newHead = head;
Node cur = head;
Node pre = null;
Node next = null;
while (cur != null) {
next = cur.next;
stack.push(cur);
if (stack.size() == K) {
pre = resign1(stack, pre, next);
newHead = newHead == head ? cur : newHead;
}
cur = next;
}
return newHead;
}
public Node resign1(Stack<Node> stack, Node left, Node right) {
Node cur = stack.pop();
if (left != null) {
left.next = cur;
}
Node next = null;
while (!stack.isEmpty()) {
next = stack.pop();
cur.next = next;
cur = next;
}
cur.next = right;
return cur;
} 方法二：不需要栈结构，在原链表中直接调整。
用变量记录每一组开始的第一个节点和最后一个节点，然后直接逆序调整，把这一组的节点都逆序。和方法一一样，同样需要注意第一组节点的特殊处理，以及之后的每个组在逆序重连之后，需要让该组的第一个节点（原来是最后一个节点）被之前组的最后一个节点连接上，将该组的最后一个节点（原来是第一个节点）连接下一个节点。
方法二的具体实现请参看如下代码中的reverseKNodes2方法。
public Node reverseKNodes2(Node head, int K) {
if (K < 2) {
return head;
}
Node cur = head;
Node start = null;
Node pre = null;
Node next = null;
int count = 1;
while (cur != null) {
next = cur.next;
if (count == K) {
start = pre == null ? head : pre.next;
head = pre == null ? cur : head;
resign2(pre, start, cur, next);
pre = start;
count = 0;
}
count++;
cur = next;
}
return head;
}
public void resign2(Node left, Node start, Node end, Node right) {
Node pre = start;
Node cur = start.next;
Node next = null;
while (cur != right) {
next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
if (left != null) {
left.next = end;
}
start.next = right;
}
删除无序单链表中值重复出现的节点
【题目】
给定一个无序单链表的头节点head，删除其中值重复出现的节点。
例如：1->2->3->3->4->4->2->1->1->null，删除值重复的节点之后为1->2->3->4->null。
请按以下要求实现两种方法。
方法1：如果链表长度为N，时间复杂度达到O(N)。
方法2：额外空间复杂度为O(1)。
【难度】
士 ★☆☆☆
【解答】
方法一：利用哈希表。时间复杂度为O(N)，额外空间复杂度为O(N)。
具体过程如下：
1．生成一个哈希表，因为头节点是不用删除的节点，所以首先将头节点的值放入哈希表。
2．从头节点的下一个节点开始往后遍历节点，假设当前遍历到cur节点，先检查cur的值是否在哈希表中，如果在，则说明cur节点的值是之前出现过的，就将cur节点删除，删除的方式是将最近一个没有被删除的节点 pre 连接到cur的下一个节点，即pre.next=cur.next。如果不在，将cur节点的值加入哈希表，同时令pre=cur，即更新最近一个没有被删除的节点。
方法一的具体实现请参看如下代码中的removeRep1方法。
public Node {
public int value;
public Node next;
public Node(int data) {
this.value = data;
}
}
public void removeRep1(Node head) {
if (head == null) {
return;
}
HashSet<Integer> set = new HashSet<Integer>();
Node pre = head;
Node cur = head.next;
set.add(head.value);
while (cur != null) {
if (set.contains(cur.value)) {
pre.next = cur.next;
} else {
set.add(cur.value);
pre = cur;
}
cur = cur.next;
}
} 方法二：类似选择排序的过程，时间复杂度为O(N2)，额外空间复杂度为O(1)。
例如，链表1->2->3->3->4->4->2->1->1->null。
首先是头节点，节点值为1，往后检查所有值为1的节点，全部删除。链表变为：1->2->3->3->4->4->2->null。
然后是第二个节点，节点值为2，往后检查所有值为2的节点，全部删除。链表变为：1->2->3->3->4->4->null。
接着是第三个节点，节点值为3，往后检查所有值为3的节点，全部删除。链表变为：1->2->3->4->4->null。
最后是第四个节点，节点值为4，往后检查所有值为4的节点，全部删除。链表变为：1->2->3->4->null。
删除过程结束。
方法二的具体实现请参看如下代码中的removeRep2方法。
public void removeRep2(Node head) {
Node cur = head;
Node pre = null;
Node next = null;
while (cur != null) {
pre = cur;
next = cur.next;
while (next != null) {
if (cur.value == next.value) {
pre.next = next.next;
} else {
pre = next;
}
next = next.next;
}
cur = cur.next;
}
} <p> 本专刊为左程云书《程序员代码面试指南》前三章，已获得官方授权，想看书中更多内容可去购买书籍查看。 同时点击可查看牛客算法笔面试真题精讲班，每周由左老师讲解经典高频校招题目：https://www.nowcoder.com/courses/cover/live/350 本专刊购买后即可解锁所有章节，故不可以退换哦~ </p> <p> <br /> </p>
腾讯公司福利 448人发布
