Loading... # 两个单链表是否相交 两个有环或者无环的单链表是否相交 ## 判断一个单链表是否有环  **如何判断一个单链表是否有环？有两种方式：** ### hashSet 可以从头结点开始遍历，每遍历一个节点，判断set中有没有该节点，如果没有就放入set中，如果有就说明链表有环，然后直接返回，如果遍历完set中都没有重复的节点，说明链表无环。 ### 双指针 定义两个指针，一个fast快指针，每次走两步，一个slow指针，每次走一步，如果链表有环，两个指针必定会在某一节点处相交，如果遍历完都没有相交，说明链表无环。 **如何判断一个单链表有环，并返回入环的第一个节点** 双指针方法如果有环，必然会在某节点相交，这时让fast指针回到头结点，然后从头开始每次走一步，同时slow指针也每次走一步，直到fast与slow再次相交，相交节点就是入环的第一个节点。 ```java public static Node isLoop(Node head) { if (head == null || head.next == null || head.next.next == null) { return null; } Node fast = head.next.next; Node slow = head.next; while (fast != null && fast.next != null) { fast = fast.next.next; slow = slow.next; if (fast == slow) { break; } } if (fast != slow) { return null; } fast = head; while (fast != slow) { fast = fast.next; slow = slow.next; } return slow; } ``` ## 判断链表是否相交，并返回相交的第一个节点 有三种情况： 1. 两链表均无环 2. 一个链表有环，一个链表无环 3. 两个链表均有环 ### 两链表均无环   如上两张图，两个无环单链表，要么完全不相交，要么因为指针只能是单向的，相交就不会再出来，所以一定会共用相交之后的部分。 所以，只需要同时从头遍历两个链表，并记录长度，如果两个链表的最后一个节点不相同，说明两个链表不相交。如果相同，说明相交，再次从头遍历两个链表，让比较长的链表先遍历两链表长度差的步数，然后再同时每次遍历一步，直到两链表的节点相同，这时就获取到了第一个相交的节点。 ```java Node loop1 = isLoop(head1); Node loop2 = isLoop(head2); if (loop1 == null && loop2 == null) { Node cur1 = head1; int n = 0; while (cur1.next != null) { cur1 = cur1.next; n++; } Node cur2 = head2; while (cur2.next != null) { cur2 = cur2.next; n--; } if (cur1 != cur2) { return null; } cur1 = n > 0 ? head1 : head2; cur2 = n > 0 ? head2 : head1; n = Math.abs(n); while (n > 0) { cur1 = cur1.next; n--; } while (cur1 != cur2) { cur1 = cur1.next; cur2 = cur2.next; } return cur1; } ``` ### 一个链表无环，一个链表有环 由于单链表只有一个方向的指针，只要相交，就不能出来，因此一个有环，一个无环的链表是不可能相交的。 ### 两个链表均有环 两个有环链表相交一定会共用该环，但是有两种情况 **两个链表入环节点相同**  这种情况我们可以舍弃环，以入环节点为最终节点，直接按照两个无环链表的方式处理。 ```java Node loop1 = isLoop(head1); Node loop2 = isLoop(head2); if (loop1 != null && loop2 != null) { if (loop1 == loop2) { Node cur1 = head1; int n = 0; while (cur1 != loop1) { cur1 = cur1.next; n++; } Node cur2 = head2; while (cur2 != loop2) { cur2 = cur2.next; n--; } cur1 = n > 0 ? head1 : head2; cur2 = n > 0 ? head2 : head1; n = Math.abs(n); while (n > 0) { cur1 = cur1.next; n--; } while (cur1 != cur2) { cur1 = cur1.next; cur2 = cur2.next; } return cur1; } } ``` **两个链表入环节点不相同**   如上两张图，入环节点不相同可能会有两种情况： 1. 两个有环链表相交，此时3节点与5节点都算是相交的第一个节点。 2. 两个有环链表不相交 如何辨别如上两种情况？只需要从两个入环节点的其中一个遍历，如果遇到与另一个节点相等，说明两链表相交，如果转了一圈也不相等说明两链表不相交。 ```java Node loop1 = isLoop(head1); Node loop2 = isLoop(head2); if (loop1 != null && loop2 != null) { if (loop1 != loop2) { Node cur = loop1.next; while (cur != loop1) { cur = cur.next; if (cur == loop2) { return cur; } } return null; } } ``` Last modification：July 16th, 2022 at 10:27 pm © 允许规范转载
