有环单链表相交判断练习题

题目

如何判断两个有环单链表是否相交？相交的话返回第一个相交的节点，不想交的话返回空。如果两个链表长度分别为N和M，请做到时间复杂度O(N+M)，额外空间复杂度O(1)。
给定两个链表的头结点head1和head2，请返回一个bool值代表它们是否相交。

思路

一共有三种相交的情况：

1. 在入环的节点相交
2. 在入环的节点之前相交
3. 在环中相交

解题的关键在于先拿到如环的节点，然后即可对三种情况进行判断

答案

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;
}