题目
给定两个可能有环也可能无环的单链表，头节点head1和head2。
请实现一个函数，如果两个链表相交，请返回相交的第一个节点。如果不相交，返回null。
要求：如果两个链表长度之和为N，时间复杂度请达到O(N)，额外空间复杂度请达到O(1)
思路： 如果要解决上面的问题，就需要会：
- 如何判定有环并找到链表第一个入环节点
- 链表相交的情况
如何判定有环并找到链表第一个入环节点
1.使用额外空间Set
2.快慢指针法
如果有环，快慢指针肯定会相遇，并且转的圈数不超过两圈，因为快指针的速度是慢指针的两倍，在慢指针转完一圈时如果还没相遇就是无环，如果有环在慢指针转完一圈之前肯定会在环上相遇。 相遇之后，慢指针以这个相遇点为起点，快指针以链表头为起点，然后两个指针保持速度一致，每次只走一步，相遇的点就是入环的第一个节点处。
// 找到链表第一个入环节点，如果无环，返回null public static Node getLoopNode(Node head){ if(head == null || head.next == null || head.next.next == null){ return null; } Node n1 = head.next; // n1 -> show 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; } 复制代码
两个链表是否相交
1.两个链表都无环的情况
分析
如果两个链表都是无环，如果相交那么就是"Y"型，也就是说，两个链表的后半部分是相同部分。不可能是"X"型，因为是单链表只会有一个next指针，如果是"X"型，就肯定会有一个节点有两个next指针，这是不合理的。
思路
- 1.先判断两个链表的尾部节点是否是同一个，如果不是就说明不相交，如果是进入第2个判断
- 2.求出两个链表的长度差n，较长的链表先走n步后，两个链表再一起走，相遇的第一个点就是相交的点。
// 如果两个链表都无环，返回第一个相交节点，如果不相交，返回null public static Node noLoop(Node head1, Node head2){ if(head1 == null || head2 == null){ return null; } Node cur1 = head1; Node cur2 = head2; int n = 0; // 长度，遍历链表1的时候n++，遍历链表2的时候n--，最后的值就是链表1与2的长度差 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; // 谁长，谁的头变cur1 cur2 = cur1 == head1 ? head2 : head1; // 谁短，谁的头变成cur2 n = Math.abs(n); while(n != 0){ n--; cur1 = cur1.next; } while(cur1 != cur2){ cur1 = cur1.next; cur2 = cur2.next; } return cur1; } 复制代码
2.一个链表无环，另一个链表有环的情况
这种情况不存在相交的情况
3.两个链表都有环的情况
两个链表都有环，主要分为下面三种情况：
- 1）不相交，各自成环
- 2）相交，共用环，入环节点是同一个
- 3）相交，共用环，入环节点不是同一个
网络异常，图片无法展示
|
实现思路
- 首先判断入环节点是否同一个，即loop1是否等于loop2，如果是就是第二种情况
- loop1继续转圈，如果在转的过程中能遇到loop2，就是情况三，否则就是情况一
// 两个有环链表，返回第一个相交节点，如果不相交返回null public static 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; } } // 主函数 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 noLoop(head1, head2); } if(loop1 != null && loop2 != null){ return bothLoop(head1, loop1, head2, loop2); } return null; }
