【算法】两个单链表相交，返回相交的第一个节点---MapleYe

题目

在本题中，单链表可能有环，也可能无环。 给定两个 单链表的头节点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; } ---来自腾讯云社区的---MapleYe