【算法】两个单链表相交，返回相交的第一个节点
题目
在本题中，单链表可能有环，也可能无环。 给定两个 单链表的头节点head1和head2，这两个链表可能相交，也可能不相交。 请实现一个函数，如果两个链表相交，请返回相交的第一个节点; 如果不相交，返回null即可。 要求: 如果链表1的长度为N，链表2的长度为M，时间复杂度请达到 O(N+M)，额外空间复杂度请达到O(1)
链表结构如下：
public static class Node {
public Node next;
public int value;
public Node(int data) {
value = data;
}
}思路
1、先判断两个链表有环，或者无环，有环则返回入环节点，否则为null
定理查找
若链表有两个指针，慢指针，一次跳1个节点，快指针一次跳2个节点，若链表成环。那么快节点一定会跟慢节点相遇。 相遇后，快节点回到头部，然后1个1个节点的走，直至和慢节点相遇，那么这时候相遇的节点就是要找的循环开始节点
算法实现
public static Node getLoopNode(Node head) {
// 小于2个节点的链表不可能组成环形
if(head == null || head.next == null || head.next.next == null) {
return null;
}
// 慢节点，一次跳1个节点
Node n1 = head.next;
// 快节点，一次跳2个节点
Node n2 = head.next.next;
// 定理：若链表成环，那么快节点一定会跟慢节点相遇
while(n1 != n2) {
if(n2.next == null || n2.next.next == null) {
return null;
}
n2 = n2.next.next;
n1 = n1.next;
}
// 相遇后，快节点回到头部，然后1个1个节点的走，直至和n1相遇
// 那么这时候相遇的节点就是要找的循环开始节点
n2 = head;
while(n1 != n2) {
n2 = n2.next;
n1 = n1.next;
}
return n1;
}额外空间法-哈希表
若没有空间复杂度要求的话，这里的有无环判断，可以通过哈希表判断。链表开始从头遍历至末尾，先查表，若无则把Node放进表里，以Node为key，Node为值放入哈希表中。若从表中查到节点，那么第一个查到的节点就是入环节点。
算法实现
public static Node getLoopNode2(Node head) {
HashMap<Node, Node> map = new HashMap<Node, Node>();
while(head != null) {
if (map.get(head) != null ) {
return head;
}else {
map.put(head, head);
}
head = head.next;
}
return null;
}2、分析两个链表列表有环，无环的情况
2.1、1个链表有环，1个链表无环
结论：永远不可能相交
2.2、两个链表都无环
若相交，那么必然如图所示：
两个无环链表相交情况
那么，针对以上结构，我们可以这样处理 1、判断哪个链表更长，把长链表从头节点开始一直指向下一个节点，直至与短链表长度一直 2、长短链表长度相等后，各种开始指向下一个节点，同时判断当前两个指针指向的节点是否相等，期间第一个相等的节点，即为第一个相交的节点。若遍历到结尾都不相等，则两个链表没有相交的节点。
算法实现
public static Node noLoop1(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;
}
// n>0说明head1较长
// 以下步骤是cur1指向较长的链表，cur2指向较短的链表
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;
}若没有空间复杂度要求，我们可以使用HashMap来存储其中一个链表，另外一个链表遍历比较，实现如下：
public static Node noLoop2(Node head1, Node head2) {
HashMap<Node, Node> map = new HashMap<Node, Node>();
while(head1 != null) {
map.put(head1, head1);
head1 = head1.next;
}
while(head2 != null) {
if (map.get(head2) != null) {
return head2;
}
head2 = head2.next;
}
return null;
}2.3、两个链表都有环
若两个链表有环且相交，只可能出现两种情况。
情况1
两个有环链表相遇情况1
如图所示，第一个相交结点必然不是环结点，而是入环前的节点。那么我们可以抹去成环部分，就可以转为两个无环链表的相交的问题了。
情况2
两个有环链表相遇情况2
如图所示，若是情况2，那么只需遍历L1的loop1，直至回到loop1，期间若与loop2相遇，那么两个链表的第一个相遇节点就是loop1或loop2。否则不相交
算法实现
public static Node bothLoop(Node head1, Node loop1, Node head2, Node loop2) {
Node cur1 = null;
Node cur2 = null;
// 这时候两个链表构成的形状是 >-O
// 这时候可以忽略环，转换为求两个无环链表的相交问题
if (loop1 == loop2) {
// 情况1
cur1 = head1;
cur2 = head2;
int n = 0;
// 只遍历到loop1
while(cur1.next != loop1) {
n++;
cur1 = cur1.next;
}
// 只遍历到loop2
while(cur2.next != 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 {
// 情况2
cur1 = loop1.next;
while(cur1 != loop1) {
if(cur1 == loop2) {
return loop1;
}
cur1 = cur1.next;
}
return null;
}
}完整代码
public static 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 noLoop1(head1, head2);
}
if (loop1 != null && loop2 != null) {
return bothLoop(head1, loop1, head2, loop2);
}
// 一个链表有环，一个链表无环，是不可能相交的
return null;
}
/// 处理两个链表无环的情况
/// 先把两个链表中，较长的链表走到跟较短的链表一样长
/// 最后两个链表一起走，第一相遇的节点，就是第一个相交节点
public static Node noLoop1(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;
}
// n>0说明head1较长
// 以下步骤是cur1指向较长的链表，cur2指向较短的链表
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;
}
/// 处理两个链表有环的情况
public static Node bothLoop(Node head1, Node loop1, Node head2, Node loop2) {
Node cur1 = null;
Node cur2 = null;
// 这时候可以忽略环，转换为求两个无环链表的相交问题
if (loop1 == loop2) {
// 情况1
cur1 = head1;
cur2 = head2;
int n = 0;
// 只遍历到loop1
while(cur1.next != loop1) {
n++;
cur1 = cur1.next;
}
// 只遍历到loop2
while(cur2.next != 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 {
// 情况2
cur1 = loop1.next;
while(cur1 != loop1) {
if(cur1 == loop2) {
return loop1;
}
cur1 = cur1.next;
}
return null;
}
}
/// 获得环形链表的循环开始的节点
public static Node getLoopNode(Node head) {
// 小于2个节点的链表不可能组成环形
if(head == null || head.next == null || head.next.next == null) {
return null;
}
// 慢节点，一次跳1个节点
Node n1 = head.next;
// 快节点，一次跳2个节点
Node n2 = head.next.next;
// 定理：若链表成环，那么快节点一定会跟慢节点相遇
while(n1 != n2) {
if(n2.next == null || n2.next.next == null) {
return null;
}
n2 = n2.next.next;
n1 = n1.next;
}
// 相遇后，快节点回到头部，然后1个1个节点的走，直至和n1相遇
// 那么这时候相遇的节点就是要找的循环开始节点
n2 = head;
while(n1 != n2) {
n2 = n2.next;
n1 = n1.next;
}
return n1;
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录