问题：
给定两个链表的头结点，head1，head2，链表可能有环可能无环。这两个链表可能相交可能不相交。请实现一个函数，如果相交，返回相交的第一个节点，如果不相交返回null，如果链表长度分别为m，n要求时间复杂度O（m+n），额外空间复杂度O（1）
此问题可以拆分成三个子问题：
1.判断链表有环无环，有环，返回入环的第一个节点。无环，返回null
2.如果两个链表都无环，实现一个方法：返回两个无环链表相交的第一个节点（如果相交就为Y型结构）
3.如果两个链表都有环并且知道入环的第一个节点。返回相交第一个节点
其他情况链表不可能相交。
问题一与问题二都有两种解法：1.借助hashMap，hashSet额外空间复杂度O（n）或者2.借助指针变量额外空间复杂度O（1）
问题三：两个有环链表三种情况：不相交，入环前相交，入环后相交
loop为入环节点
问题一：方法1：
//判断链表有没有环，如果有返回入口节点
//方法一：额外空间复杂度O（N），借助了hashMap(正确)
public static ListNode EntryNodeOfLoop(ListNode pHead)
{
if(pHead==null) return null;
HashSet<ListNode> hs=new HashSet<ListNode>();
ListNode p=pHead;
while(hs.add(p)) {
if(p.next==null) return null;//遍历到最后一个节点都没有遇见重复的就返回空，并没有环
else
p=p.next;
}
//如果p已经进入了hashSet，则hs.add（p）会返回false此时p即为入口的第一个节点
return p;
}方法2：
//方法二，额外空间复杂度o（1）两个指针完成（正确）
public static ListNode EntryNodeOfLoop2(ListNode pHead)
{
if(pHead==null||pHead.next==null||pHead.next.next==null) return null;
ListNode fast=pHead;
ListNode slow=pHead;
//快慢指针开始走，如果相遇，break
while(fast!=null&&fast.next!=null) {
fast=fast.next.next;
slow=slow.next;
if(fast==slow) break;
}
//如果快指针走到终点都没有相遇就没有环
if(fast==null||fast.next==null)
return null;
//快指针调整初始位置和速度，返回第二次相遇位置即入环节点
fast=pHead;
while(fast!=slow) {
fast=fast.next;
slow=slow.next;
}
return fast;
}问题二：
方法一：
//两个无环链表相交方法一借助hashSet 额外空间O（N）返回相交的第一个结点或者null(正确)
public static ListNode Noloop1(ListNode head1,ListNode head2){
if(head1==null||head2==null) return null;
HashSet<ListNode>hs=new HashSet<ListNode>();
ListNode p=head1;
//将链表1所有节点放入hs中
while(p!=null) {
hs.add(p);
p=p.next;
}
p=head2;
while(p!=null) {
if(hs.contains(p)) return p;
p=p.next;
}
return null;
}方法2：
//两个无环链表相交方法二 借助快慢指针额外空间O（1） 返回相交的第一个节点或者null（正确）
//遍历一遍，分别得到两个链表长度，如果尾节点不一致，一定不相交。如果尾节点一致，需要在遍历一遍找到第一个相交位置
//遍历第二遍时，长节点先走差值步，然后一起走，直到两个节点相遇
public static ListNode Noloop2(ListNode head1,ListNode head2) {
//
if(head1==null||head2==null) return null;
int length1=0,length2=0;
ListNode p1=head1;
ListNode p2=head2;
while(p1.next!=null) {
p1=p1.next;
length1++;
}
while(p2.next!=null) {
p2=p2.next;
length2++;
}
//两个链表不相交
if(p1!=p2) return null;
length1=length1-length2;
p1=length1>0?head1:head2;
p2= p1==head1?head2:head1;//p1指向长链表
length1=Math.abs(length1);
while(length1!=0) {
length1--;
p1=p1.next;
}
//代码执行到这里两个链表一定有交点
while(p1!=null) {
if(p1==p2) return p1;
p1=p1.next;
p2=p2.next;
}
return null;
}问题三：
代码：
//loop为有环链表的入环节点
//两个有环链表相交，返回相交的第一个节点或者null，额外空间O（1）不借助额外数据结构
public static ListNode Bothloop(ListNode head1,ListNode loop1,ListNode head2,ListNode loop2) {
//传入的参数是两个链表头结点，两个链表第一个入环节点
//两个带环的链表有三种情况
if(loop1==loop2) {//一定相交，找出第一个相交节点返回Y型结构加一个环
//得到链表长度（head到入环位置），然后长链表走差值步，然后一起走到相交位置
int length1=0;
int length2=0;
ListNode p1=head1;
ListNode p2=head2;
while(p1!=loop1) {
length1++;
p1=p1.next;
}
while(p2!=loop1) {
length2++;
p2=p2.next;
}
length1=length1-length2;
p1= length1>0?head1:head2;//p1指向较长链表
p2= p1==head1?head2:head1;
length1=Math.abs(length1);
while(length1!=0) {
length1--;
p1=p1.next;
}
while(p1!=loop1) {
if(p1==p2) return p1;
p1=p1.next;
p2=p2.next;
}
return p1;
}
else {
//loop1顺链表走，如果能遇到loop2返回loop1或者loop2为相交节点，
如果走回原loop1位置都没有遇到loop2即不相交
ListNode p=loop1.next;
while(p!=loop1) {
if(p==loop2) return loop2;//相交返回loop1或者loop2
p=p.next;
}
return null;//不相交
}
}
得到两个链表，求相交节点：
//得到两个链表相交的第一个交点
private static ListNode getIntersectNode(ListNode head1, ListNode head2) {
if(head1==null||head2==null) return null;
//判断是否有环 如果有返回入环节点
ListNode loop1=EntryNodeOfLoop(head1);
ListNode loop2=EntryNodeOfLoop(head2);
//两个无环链表
if(loop1==null&&loop2==null) {
System.out.println(loop1+","+loop2);
System.out.println("进入Noloop函数");
return Noloop1(head1,head2);
//Noloop2(head1,head2);
}//两个有环链表
else if(loop1!=null&&loop2!=null) {
System.out.println("两个有环链表入环节点："+loop1.value+","+loop2.value);
return Bothloop(head1, loop1, head2, loop2);
}
return null;
}（end）
完整代码：
package ListNode;
import java.util.HashSet;
public class FirstInterNode {
public static class ListNode{
int value;
ListNode next;
ListNode(int a){this.value=a;}
}
//判断链表有没有环，如果有返回入口节点
//方法一：额外空间复杂度O（N），借助了hashMap(正确)
public static ListNode EntryNodeOfLoop(ListNode pHead)
{
if(pHead==null) return null;
HashSet<ListNode> hs=new HashSet<ListNode>();
ListNode p=pHead;
while(hs.add(p)) {
if(p.next==null) return null;//遍历到最后一个节点都没有遇见重复的就返回空，并没有环
else
p=p.next;
}
//如果p已经进入了hashSet，则hs.add（p）会返回false此时p即为入口的第一个节点
return p;
}
//方法二，额外空间复杂度o（1）两个指针完成（正确）
public static ListNode EntryNodeOfLoop2(ListNode pHead)
{
if(pHead==null||pHead.next==null||pHead.next.next==null) return null;
ListNode fast=pHead;
ListNode slow=pHead;
//快慢指针开始走，如果相遇，break
while(fast!=null&&fast.next!=null) {
fast=fast.next.next;
slow=slow.next;
if(fast==slow) break;
}
//如果快指针走到终点都没有相遇就没有环
if(fast==null||fast.next==null)
return null;
//快指针调整初始位置和速度，返回第二次相遇位置即入环节点
fast=pHead;
while(fast!=slow) {
fast=fast.next;
slow=slow.next;
}
return fast;
}
//两个无环链表相交方法一借助hashSet 额外空间O（N）返回相交的第一个结点或者null(正确)
public static ListNode Noloop1(ListNode head1,ListNode head2){
if(head1==null||head2==null) return null;
HashSet<ListNode>hs=new HashSet<ListNode>();
ListNode p=head1;
//将链表1所有节点放入hs中
while(p!=null) {
hs.add(p);
p=p.next;
}
p=head2;
while(p!=null) {
if(hs.contains(p)) return p;
p=p.next;
}
return null;
}
//两个无环链表相交方法二 借助快慢指针额外空间O（1） 返回相交的第一个节点或者null（正确）
//遍历一遍，分别得到两个链表长度，如果尾节点不一致，一定不相交。如果尾节点一致，需要在遍历一遍找到第一个相交位置
//遍历第二遍时，长节点先走差值步，然后一起走，直到两个节点相遇
public static ListNode Noloop2(ListNode head1,ListNode head2) {
//
if(head1==null||head2==null) return null;
int length1=0,length2=0;
ListNode p1=head1;
ListNode p2=head2;
while(p1.next!=null) {
p1=p1.next;
length1++;
}
while(p2.next!=null) {
p2=p2.next;
length2++;
}
//两个链表不相交
if(p1!=p2) return null;
length1=length1-length2;
p1=length1>0?head1:head2;
p2= p1==head1?head2:head1;//p1指向长链表
length1=Math.abs(length1);
while(length1!=0) {
length1--;
p1=p1.next;
}
//代码执行到这里两个链表一定有交点
while(p1!=null) {
if(p1==p2) return p1;
p1=p1.next;
p2=p2.next;
}
return null;
}
//loop为有环链表的入环节点
//两个有环链表相交，返回相交的第一个节点或者null，额外空间O（1）不借助额外数据结构
public static ListNode Bothloop(ListNode head1,ListNode loop1,ListNode head2,ListNode loop2) {
//传入的参数是两个链表头结点，两个链表第一个入环节点
//两个带环的链表有三种情况
if(loop1==loop2) {//一定相交，找出第一个相交节点返回Y型结构加一个环
//得到链表长度（head到入环位置），然后长链表走差值步，然后一起走到相交位置
int length1=0;
int length2=0;
ListNode p1=head1;
ListNode p2=head2;
while(p1!=loop1) {
length1++;
p1=p1.next;
}
while(p2!=loop1) {
length2++;
p2=p2.next;
}
length1=length1-length2;
p1= length1>0?head1:head2;//p1指向较长链表
p2= p1==head1?head2:head1;
length1=Math.abs(length1);
while(length1!=0) {
length1--;
p1=p1.next;
}
while(p1!=loop1) {
if(p1==p2) return p1;
p1=p1.next;
p2=p2.next;
}
return p1;
}
else {
//loop1顺链表走，如果能遇到loop2返回loop1或者loop2为相交节点，如果走回原loop1位置都没有遇到loop2即不相交
ListNode p=loop1.next;
while(p!=loop1) {
if(p==loop2) return loop2;//相交返回loop1或者loop2
p=p.next;
}
return null;//不相交
}
}
public static void main(String []args) {
// 1->2->3->4->5->6->7->null
ListNode head1 = new ListNode(1);
head1.next = new ListNode(2);
head1.next.next = new ListNode(3);
head1.next.next.next = new ListNode(4);
head1.next.next.next.next = new ListNode(5);
head1.next.next.next.next.next = new ListNode(6);
head1.next.next.next.next.next.next = new ListNode(7);
// 0->9->8->6->7->null
ListNode head2 = new ListNode(0);
head2.next = new ListNode(9);
head2.next.next = new ListNode(8);
head2.next.next.next = head1.next.next.next.next.next; // 8->6
System.out.println(getIntersectNode(head1, head2).value);
// 1->2->3->4->5->6->7->4...
head1 = new ListNode(1);
head1.next = new ListNode(2);
head1.next.next = new ListNode(3);
head1.next.next.next = new ListNode(4);
head1.next.next.next.next = new ListNode(5);
head1.next.next.next.next.next = new ListNode(6);
head1.next.next.next.next.next.next = new ListNode(7);
head1.next.next.next.next.next.next.next = head1.next.next.next; // 7->4
// 0->9->8->2...
head2 = new ListNode(0);
head2.next = new ListNode(9);
head2.next.next = new ListNode(8);
head2.next.next.next = head1.next; // 8->2
System.out.println(getIntersectNode(head1, head2).value);
//0->9->8->6->7...
/*ListNode head2 = new ListNode(0);
head2.next = new ListNode(9);
head2.next.next = new ListNode(8);
head2.next.next.next = head1.next.next.next.next.next; // 8->6
System.out.println(getIntersectNode(head1, head2).value);*/
}
//得到两个链表相交的第一个交点
private static ListNode getIntersectNode(ListNode head1, ListNode head2) {
if(head1==null||head2==null) return null;
//判断是否有环 如果有返回入环节点
ListNode loop1=EntryNodeOfLoop(head1);
ListNode loop2=EntryNodeOfLoop(head2);
//两个无环链表
if(loop1==null&&loop2==null) {
System.out.println(loop1+","+loop2);
System.out.println("进入Noloop函数");
return Noloop1(head1,head2);
//Noloop2(head1,head2);
}//两个有环链表
else if(loop1!=null&&loop2!=null) {
System.out.println("两个有环链表入环节点："+loop1.value+","+loop2.value);
return Bothloop(head1, loop1, head2, loop2);
}
return null;
}
}
版权声明：本文为qq_37290134原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。