必会算法：链表相交问题
链表节点定义如下
public class Node {
public Integer value;
public Node next;
public Node() {
}
public Node(Integer value) {
this.value = value;
}
public Node(Integer value, Node next) {
this.value = value;
this.next = next;
}
@Override
public String toString() {
Node temp = this;
StringBuilder str = new StringBuilder();
while (temp != null) {
str.append(temp.value).append("->");
temp = temp.next;
}
str.append("null");
return str.toString();
}
}题目
如何判断两个链表是否相交呢？
如果相交，那么请找出相交节点。
判断链表相交
首先我们得清楚一点
链表相交和两条直线相交不同
因为链表的后继节点只能有一个
所以相交的情况只能是下图中的情况1、情况2、情况3
所以链表相交的情况可以通过下图表示
L1部分最短可以为0，对应情况3
C部分最短可以为1，对应情况2
解题思路
根据上边分析的情况1、情况2和情况3
如果链表相交，则最末尾的非null节点一定是同一个
所以只需要遍历两条链表
比较最后一个节点是否相同就行了
相同，则两条链表必定相交
不相同，则一定不相交
代码实现
public static Boolean isLinkedListCross(Node node1, Node node2) {
if (node1 == null || node2 == null) {
return false;
}
if (node1 == node2) {
return true;
}
// 同时遍历两个链表，如果最后一个节点是同一个，那么肯定相交
while (node1.next != null || node2.next != null) {
if (node1.next != null) {
node1 = node1.next;
}
if (node2.next != null) {
node2 = node2.next;
}
}
return node1 == node2;
}找到链表相交点
判断是否相交很简单
稍微上点难度的就是找到相交点
当然如果不考虑空间复杂度
遍历一个链表，并将各个节点使用HashSet存储
然后再遍历另外一个链表
判断第一个被HashSet包含的节点就是相交点
那么有没有看起来稍微高级一点的解题方法呢？
方法1
其实这道题有点像判断链表是否存在环
之后找出环开始节点的那道题
在判定链表一定相交的情况下
list1从“1”节点开始遍历
当到达尾部时，则从“1”节点开始遍历
list1从“A”节点开始遍历
当到达尾部时，则从“A”节点继续遍历
在遍历速度相同的情况下
如果list1和list2的长度相同
那么在第一轮遍历的时候就能直接找到相交点
如果list1和list2的长度不同
那么必定是L1部分和L2部分的长度不同
两条链表的遍历周期也必然不同
所以同速遍历的情况下，多轮遍历后
短的链表必然会追上长的链表
而C部分又是相同的共有部分
所以第一次的追上的节点必定是在C部分开头
即两条链表的相交点
代码实现如下
public static Node findLinkedListCross(Node node1, Node node2) {
Node head1 = node1;
Node head2 = node2;
// 循环遍历，总归会相交，第一次相交点就是node1和node2第一次相等的时候
while (node1 != node2) {
node1 = node1 == null ? head1 : node1.next;
node2 = node2 == null ? head2 : node2.next;
}
return node1;
}方法2
接着方法1的思路，我们可以做一下优化
方法1是通过遍历两个周期不同链表找到相交点
这种方法的本质就是让短的去追长的
如果链表相差比较多，可能需要多轮循环才能找到相交点
那有没有办法尽量减小循环的轮次呢？
还真有！
如果我们在list1遍历到尾部的时候
接下来从list2的头部开始遍历
在list2遍历到尾部的时候
接下来从list1的头部开始遍历
那么两个链表的遍历岂不是即周期相同也速度相同了吗？
这样只需要经过（l1+l2+c）三个部分的长度次遍历
就能顺利地找到相交节点“5”了
代码实现
public static Node findLinkedListCross2(Node node1, Node node2) {
Node head1 = node1;
Node head2 = node2;
// 循环遍历，两遍下来，
// 遍历的路程肯定是一样的，除去最后相交的那一段，第一个相等点就是相交点
while (node1 != node2) {
node1 = node1 == null ? head2 : node1.next;
node2 = node2 == null ? head1 : node2.next;
}
return node1;
}方法3
通过上边的分析我们能够知道
当两条链表的长度相等的时候
是最简单的情况
这个时候只需要两条链表都同时从头开始遍历
经过非公共部分之后就能顺利找到相交点
所以我们只要找出L21部分的长度
就可以将问题简化为两条长度相等的相交链表了
而找到L21部分的长度也非常简单
只需要求出两条链表的长度
相减的绝对值就是L21部分的长度了
代码实现
public static Node findLinkedListCross3(Node node1, Node node2) {
int len1 = 0;
int len2 = 0;
//对比两条链表的长度
Node temp1 = node1;
Node temp2 = node2;
while (temp1 != null) {
len1++;
temp1 = temp1.next;
}
while (temp2 != null) {
len2++;
temp2 = temp2.next;
}
// 将两条链表截成等长
temp1 = node1;
temp2 = node2;
if (len1 > len2) {
for (int i = 0; i < len1 - len2; i++) {
temp1 = temp1.next;
}
} else if (len1 < len2) {
for (int i = 0; i < len2 - len1; i++) {
temp2 = temp2.next;
}
}
// 遍历等长的相交链表，第一次节点相等，即为相交点
while (temp1 != temp2) {
temp1 = temp1.next;
temp2 = temp2.next;
}
return temp1;
}虽然代码看起来不那么简练
但却是最容易理解的解法
测试验证
接下来验证一下
public static void main(String[] args) {
Node node1 = new Node(1);
Node temp = node1;
for (int i = 2; i < 10; i++) {
temp.next = new Node(i);
temp = temp.next;
}
Node node2 = new Node(1);
temp = node2;
for (int i = 2; i < 6; i++) {
temp.next = new Node(i);
temp = temp.next;
}
temp.next = node1.next.next.next.next;
System.out.println(isLinkedListCross(node1, node2));
System.out.println(findLinkedListCross(node1, node2));
System.out.println(findLinkedListCross2(node1, node2));
System.out.println(findLinkedListCross3(node1, node2));
}
文/戴先生@2022年02月04日
腾讯云开发者
