題目
如何判斷兩個(gè)有環(huán)單鏈表是否相交？相交的話返回第一個(gè)相交的節(jié)點(diǎn)觅闽，不想交的話返回空帝雇。如果兩個(gè)鏈表長(zhǎng)度分別為N和M，請(qǐng)做到時(shí)間復(fù)雜度O(N+M)蛉拙，額外空間復(fù)雜度O(1)尸闸。
給定兩個(gè)鏈表的頭結(jié)點(diǎn)head1和head2，請(qǐng)返回一個(gè)bool值代表它們是否相交。
思路
一共有三種相交的情況：
- 在入環(huán)的節(jié)點(diǎn)相交
- 在入環(huán)的節(jié)點(diǎn)之前相交
- 在環(huán)中相交
解題的關(guān)鍵在于先拿到如環(huán)的節(jié)點(diǎn)吮廉，然后即可對(duì)三種情況進(jìn)行判斷
答案
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);
// 第一種情況：在環(huán)的入口點(diǎn)或者環(huán)入口點(diǎn)之前就已經(jīng)相交
if (intersectNode1 == intersectNode2) {
return true;
}
// 第二種情況：在環(huán)中相交
ListNode *current = intersectNode1;
while (1) {
current = current->next;
if (current == intersectNode1) {
break;
} else if (current == intersectNode2){
return true;
}
}
return false;
}
