链接
判断两个链表是否相交
分为如下几个问题:
1.判断链表是否有环,若有返回入环节点
2.两个无环链表判断相交
3.两个有环链表判断相交
4.一个无环链表与一个有环链表必不相交
public class Solution {
/**
* 判断链表是否有环
*
* @param head
* @return 如果有环,返回入环节点,否则,返回null
*/
private static ListNode hasLoop(ListNode head) {
if (head == null || head.next == null || head.next.next == null) {
return null;
}
ListNode slow = head.next, fast = head.next.next;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
slow = head;
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
return slow;
}
}
return null;
}
/**
* 判断两个无环链表是否相交
*
* @param head1
* @param head2
* @return 第一个相交节点
*/
private static ListNode judgeTwoNoLoopList(ListNode head1, ListNode head2) {
if (head1 == null || head2 == null) {
return null;
}
int n = 0;
ListNode cur1 = head1, tail1 = head1;
while (cur1 != null) {
n++;
tail1 = cur1;
cur1 = cur1.next;
}
ListNode cur2 = head2, tail2 = head2;
while (cur2 != null) {
n--;
tail2 = cur2;
cur2 = cur2.next;
}
if (tail1 != tail2) {
return null;
}
cur1 = n > 0 ? head1 : head2;
cur2 = cur1 == head1 ? head2 : head1;
n = Math.abs(n);
while (n-- > 0) {
cur1 = cur1.next;
}
while (cur1 != null && cur2 != null) {
if (cur1 == cur2) {
return cur1;
}
cur1 = cur1.next;
cur2 = cur2.next;
}
return null;
}
/**
* 判断两个有环链表是否相交
*
* @param head1
* @param head2
* @param loop1 入环节点
* @param loop2 入环节点
* @return 第一个相交节点
*/
private static ListNode judgeTwoLoopList(ListNode head1, ListNode loop1, ListNode head2, ListNode loop2) {
if (head1 == null || head2 == null) {
return null;
}
if (loop1 == loop2) {
return loop1;
}
ListNode cur = head1.next;
while (cur != head1) {
if (cur == loop2) {
return cur;
}
cur = cur.next;
}
return null;
}
public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null && headB != null || headA != null && headB == null) {
return null;
}
ListNode loop1 = hasLoop(headA);
ListNode loop2 = hasLoop(headB);
if (loop1 == null && loop2 == null) {
return judgeTwoNoLoopList(headA, headB);
} else if (loop1 != null && loop2 != null) {
return judgeTwoLoopList(headA, loop1, headB, loop2);
}
return null;
}
}
class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
next = null;
}
@Override
public String toString() {
return "ListNode{" +
"val=" + val +
'}';
}
}