题目
如何判断两个有环单链表是否相交？相交的话返回第一个相交的节点，不想交的话返回空。如果两个链表长度分别为N和M，请做到时间复杂度O(N+M)，额外空间复杂度O(1)。
给定两个链表的头结点head1和head2，请返回一个bool值代表它们是否相交。
思路
一共有三种相交的情况：
- 在入环的节点相交
- 在入环的节点之前相交
- 在环中相交
解题的关键在于先拿到如环的节点，然后即可对三种情况进行判断
答案
ListNode* intersectNode(ListNode *head) {
ListNode *slowNode = head;
ListNode *fastNode = head;
while (fastNode->next != NULL && fastNode->next->next != NULL) {
fastNode = fastNode->next->next;
slowNode = slowNode->next;
if (slowNode == fastNode) {
fastNode = head;
while (fastNode != slowNode) {
fastNode = fastNode->next;
slowNode = slowNode->next;
}
return slowNode;
}
}
return NULL;
}
bool chkInter(ListNode* head1, ListNode* head2, int adjust0, int adjust1) {
ListNode *intersectNode1 = intersectNode(head1);
ListNode *intersectNode2 = intersectNode(head2);
// 第一种情况：在环的入口点或者环入口点之前就已经相交
if (intersectNode1 == intersectNode2) {
return true;
}
// 第二种情况：在环中相交
ListNode *current = intersectNode1;
while (1) {
current = current->next;
if (current == intersectNode1) {
break;
} else if (current == intersectNode2){
return true;
}
}
return false;
}
