两个单链表相交的一系列问题
【题目】 在本题中,单链表可能有环,也可能无环。给定两个单链表的头节点 head1和head2,这两个链表可能相交,也可能不相交。请实现一个函数, 如果两个链表相交,请返回相交的第一个节点;如果不相交,返回null 即可。
要求:如果链表1的长度为N,链表2的长度为M,时间复杂度请达到 O(N+M),额外空间复杂度请达到O(1)。
/*
* 1.如何判断单链表有环无环
* 如果单链表有环,返回第一个入环节点,如果无环,返回空,可用哈希表实现(hashset);
* 不用哈希表实现单链表有环判断,准备两个指针,快指针每次走两步,慢指针每次走一步,如果快指针在走的过程中返回null,则无环
* 如果有环,慢指针会和快指针在环上相遇,相遇后,快指针回到链表开头,每次走一步,快指针和慢指针会在入环节点处相遇。
* 2.两个无环单链表第一个相交的节点
* 哈希表实现,链表1所有节点放入map,链表2每遍历一个节点就去哈希表查一遍,第一个在的就是第一个相交节点。
* 不用hashmap:先遍历链表1,统计链表1 的长度,拿到链表1 的最后一个节点,然后遍历链表2,统计链表2 的长度,
* 拿到链表2 的最后一个节点,先判断end1是否等于end2(内存地址);如果不相等,则不可能相交,如果end1等于end2,长度较长的先走差值部分,
* 然后开始同时走,最后一起到达节点处。
* 3.两个有环单链表第一个相交的节点
* 两个有环分为三种情况,
* a.各自为环
* 如果loop1.next永远不等于loop2,则不相交
* b.先相交,然后共用一个环
* 从入环节点切分,只考虑入环前的链表,转换为两个无环单链表相交问题
* c.在一个环的不同节点入环
* loop1.next=loop2,返回loop1和loop2都可以。
*/
public class 单链表相交 { public static class Node{ public int value; public Node next; public Node(int data) { this.value = data; } } 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; } //判断是否有环,如果有环返回入环节点,否则返回空 public static Node getLoopNode(Node head) { if(head == null || head.next == null || head.next.next == null) { return null; } Node n1 = head.next; //慢节点 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; } n2 = head; //快节点返回头部 while(n1 != n2) { n1 = n1.next; n2 = n2.next; } return n1; } //两个无环单链表判断交点 public static Node noLoop(Node head1, Node head2) { if(head1 == null || head2 == null) { return null; } Node c1 = head1; Node c2 = head2; int n = 0; while(c1.next != null) { n++; c1 = c1.next; } while(c2.next != null) { n--; c2 = c2.next; } if(c1 != c2) { return null; } c1 = n > 0 ? head1 : head2; c2 = c1 == head1 ? head2 : head1; n = Math.abs(n); while(n != 0) { n--; c1 = c1.next; } while(c1 != c2) { c1 = c1.next; c2 = c2.next; } return c1; } //两个有环单链表的相交节点 public static Node bothLoop(Node head1, Node loop1, Node head2, Node loop2) { Node c1 = null; Node c2 = null; if(loop1 == loop2) { c1 = head1; c2 = head2; int n = 0; while(c1.next != loop1) { n++; c1 = c1.next; } while(c2.next != loop2) { n--; c2 = c2.next; } c1 = n > 0 ? head1 : head2; c2 = c1 == head1 ? head2 : head1; n = Math.abs(n); while(n != 0) { n--; c1 = c1.next; } while(c1 != c2) { c1 = c1.next; c2 = c2.next; } return c1; }else { c1 = loop1.next; while(c1 != loop1) { if(c1 == loop2) { return loop1; } c1 = c1.next; } } return null; } public static void main(String[] args) { } }