1.1 链表是否有环
思路：
1.快指针一次走2步，慢指针一次走一步
2.如果没有环，遍历到最后，返回null
3.如果有环，必然会在环中相遇，然后快指针回到头，快慢指针一次走一步
4.再次相遇的节点就是入环点
public static ListNode getLoopNode(ListNode head){
if(head == null){
return null;
}
ListNode slow = head;
ListNode fast = head;
while (slow.next!=null && fast.next != null && fast.next.next!=null){
slow = slow.next;
fast = fast.next.next;
//如果有环，2者在环中相遇
if(slow == fast){
//快指针回到头.2者一次走一步
fast = head;
while(fast!=null && slow!=null){
//相遇的节点就是入环点
if(fast == slow){
return fast;
}
fast = fast.next;
slow = slow.next;
}
}
}
return null;
}
2.链表相交
2.1 两个无环链表是否相交
思路：如果两个链变都没有环，那么各自从头开始遍历到最后一个节点，这个节点必然是一个样的
public boolean isIntersectWithNoLoop(ListNode headA, ListNode headB){
if(headA == null || headB == null){
return null;
}
ListNode a = headA;
ListNode b = headB;
while (a.next!=null){
a = a.next;
}
while (b.next!=null){
b = b.next;
}
//证明链表相交
if(a == b){
return true;
}
return false;
}
2.2 返回两个无环链表的相交节点
思路：
- 如果不相交返回null
- 记录链表的长度la，lb，如果相交，长的链表先走|la-lb|步
- 然后在一起走，相遇的节点就是相交节点
public static ListNode getIntersectWithNoLoop(ListNode headA, ListNode headB){
if(headA == null || headB == null){
return null;
}
ListNode a = headA;
ListNode b = headB;
int la = 1;
while (a.next!=null){
a = a.next;
la++;
}
int lb = 1;
while (b.next!=null){
b = b.next;
lb++;
}
//证明链表相交
if(a == b){
int diff = Math.abs(la - lb);
a = headA;
b = headB;
if(la > lb){
//a先提前走
while(diff>0){
a = a.next;
diff--;
}
}else{
//b先提前走
while(diff>0){
b = b.next;
diff--;
}
}
//开始一起走
while(a!=null && b!=null){
if(a == b){
return a;
}
a = a.next;
b = b.next;
}
}
return null;
}
2.3 返回两个有环链表的相交节点
思路：
- 先获取2个链表的入环节点
- 如果入环节点相同，那么就是相交后再一条链路上入环的，那么根据2.2求相交节点即可
- 如果2个入环点不相同， 那么2个入环点一定是在一个环上，且相交节点就是其中一个入环点
public static ListNode getIntersectWithBothLoop(ListNode headA, ListNode loop1, ListNode headB, ListNode loop2){
if(headA == null || headB == null || loop1 == null || loop2 == null){
return null;
}
//如果入环节点相同，那么走差值结算，返回相交节点
if(loop1 == loop2){
int alength = 1;
ListNode a = headA;
while (a.next!=loop1){
a.next = a;
alength++;
}
int blength = 1;
ListNode b = headB;
while (b.next!=loop1){
b.next = b;
alength++;
}
int diff = Math.abs(alength - blength);
a = headA;
b = headB;
if(alength > blength){
while (diff!=0){
a = a.next;
diff--;
}
}else {
while (diff!=0){
b = b.next;
diff--;
}
}
//开始一起走
while(a!=null && b!=null){
if(a == b){
return a;
}
a = a.next;
b = b.next;
}
}else {
//如果在环内相遇，那么返回任意一个入环点即可
ListNode cur = loop1.next;
while (cur!=loop1){
if(cur == loop2){
return loop1;
}
cur = cur.next;
}
return null;
}
return null;
}
2.4 返回两个链表的相交节点
思路：综合2.2和2.3
- 先获取2个链表的入环点
- 如果都为null，走2.2
- 如果都不为空走，走2.3
public static ListNode getIntersectNode(ListNode headA, ListNode headB){
if(headA == null || headB == null){
return null;
}
ListNode loop1 = getLoopNode(headA);
ListNode loop2 = getLoopNode(headB);
if(loop1 == null && loop2==null){
return getIntersectWithNoLoop(headA, headB);
}
if(loop1 != null && loop2!=null){
return getIntersectWithBothLoop(headA, loop1, headB, loop2);
}
return null;
}
