题目:给定两个可能成环的单链表,头结点head1 head2.
请实现一函数,如果两个链表相交,请返回相交的一个节点,如果不相交,返回null.
我们了解一下求链表成环节点的题目.----->给定链表的头结点,返回链表的成环节点,没有返回null.
首先这道题目分别有两种做法,一种是空间复杂度为O(N)的一种
- public static Node LoopNode1(Node head){
- if(head==null){
- return head;
- }
- Set
set = new HashSet<>(); - while(head!=null){
- if(set.contains(head)){
- return head;
- }else{
- set.add(head);
- head = head.next;
- }
-
- }
- return null;
- }
首先使用Set 如果集合内存在当前节点,那么就返回,如果不存在就放进集合内.
因为如果是有环链表的成环节点早晚会遍历到.但是如果是无环链表就会遍历到null.
同时我们还有空间复杂度为O(1) 的方法
- public static Node LoopNode(Node head){
- if(head==null || head.next==null || head.next.next==null){
- return null;
- }
- Node slow = head.next;
- Node fast = head.next.next;
- while(slow!=fast){
- if(fast.next==null || fast.next.next==null){
- return null;
- }
- slow = slow.next;
- fast = fast.next.next;
- }
- fast = head;
- while(slow!=fast){
- slow = slow.next;
- fast = fast.next;
- }
- return slow;
- }
如果首先如果链表能够成环,那么一个快指针和一个满足指针肯定能在环内碰见.
证明就先省略.
那么两个链表是否成环就有多种情况,假设head1 的入环节点为loop1 ,head2的入环节点就是loop2.
那么第一种情况:
loop1==null && loop2==null
这种情况下有两种情况:
在不成环的情况下:两链表是否相交的的判断:两条链表上是否有相同的节点.
空间复制度为O(N).
-
- private static Node intersertNode1(Node head1,Node head2){
- Set
set = new HashSet<>(); - while(head1!=null){
- set.add(head1);
- head1 = head1.next;
- }
- while(head2!=null){
- if(set.contains(head2)){
- return head2;
- }else{
- head2 = head2.next;
- }
- }
- return null;
- }
这个方法就是先将其中一个链表的全部都放在集合中.另外的一个链表从头开始遍历.第一个存在链表的节点就是相交的节点.
空间复制度为O(1)
- private static Node inersertNode(Node head1,Node head2){
- Node cur1 = head1;
- int N = 0;
- while(cur1.next!=null){
- N++;
- cur1 = cur1.next;
- }
- Node cur2 = head2;
- while(cur2.next!=null){
- N--;
- cur2 = cur2.next;
- }
- if(cur1!=cur2){
- return null;
- }
- 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;
- }
这种方法的方法就是先记录各个链表的长度,然后让长链表先走差值步,然后再同时走,直到走到其中相同的节点就是相交节点.当我们记录完链表的长度后我们能判断最后一个节点.如果最后一个节点不相同就代表不是最后一个节点.
第二种情况:
loop1==null ^ loop2==null
当链表一个成环,另外一个不成环就只有一种情况.
当只有这种情况才能符合一个入环节点为空,另外一个入环节点不为空.
这种情况就直接返回null
第三种情况:
loop1 != null && loop2 !=null
这种情况下需要我们分析
当loop1==loop2 的情况下那么就是
当loop1 != loop2
- public static Node bothLoop(Node head1,Node loop1,Node head2,Node loop2){
- Node cur1 = head1;
- Node cur2 = head2;
- if(loop1==loop2){
- int N = 0;
- while(cur1!=loop1){
- cur1 = cur1.next;
- N++;
- }
- while(cur2!=loop1){
- cur2 = cur2.next;
- N--;
- }
- cur1 = N > 0 ? head1 : head2;
- cur2 = cur1==head1 ? head2 : head1;
- N = Math.abs(N);
- while(N!=0){
- 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 loop2;
- }
- cur1 = cur1.next;
- }
- return null;
- }
- }
所以我们的总的函数就是
- public static Node getInersertNode(Node head1,Node head2){
- if(head1==null ^ head2==null){
- return null;
- }
- Node loop1 = LoopNode(head1);
- Node loop2 = LoopNode(head2);
- if(loop1==null && loop2==null){
- return inersertNode(loop1,loop2);
- }else if(loop1==null ^ loop2==null){
- return null;
- }else{
- return bothLoop(head1,loop1,head2,loop2);
- }
- }
-
- private static Node LoopNode(Node head){
- if(head==null || head.next==null || head.next.next==null){
- return null;
- }
- Node slow = head.next;
- Node fast = head.next.next;
- while(slow!=fast){
- if(fast.next==null || fast.next.next==null){
- return null;
- }
- slow = slow.next;
- fast = fast.next.next;
- }
- fast = head;
- while(slow!=fast){
- slow = slow.next;
- fast = fast.next;
- }
- return slow;
- }
- private static Node inersertNode(Node head1,Node head2){
- Node cur1 = head1;
- int N = 0;
- while(cur1.next!=null){
- N++;
- cur1 = cur1.next;
- }
- Node cur2 = head2;
- while(cur2.next!=null){
- N--;
- cur2 = cur2.next;
- }
- if(cur1!=cur2){
- return null;
- }
- 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;
- }
- private static Node bothLoop(Node head1,Node loop1,Node head2,Node loop2){
- Node cur1 = head1;
- Node cur2 = head2;
- if(loop1==loop2){
- int N = 0;
- while(cur1!=loop1){
- cur1 = cur1.next;
- N++;
- }
- while(cur2!=loop1){
- cur2 = cur2.next;
- N--;
- }
- cur1 = N > 0 ? head1 : head2;
- cur2 = cur1==head1 ? head2 : head1;
- N = Math.abs(N);
- while(N!=0){
- 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 loop2;
- }
- cur1 = cur1.next;
- }
- return null;
- }
- }