C++ 笔试基础题 22 单链表相交判断练习题 牛客网5.15

链接：https://www./courses/1/5/15
来源：牛客网

给定两个单链表的头节点head1和head2，如何判断两个链表是否相交？相交的话返回true，不想交的话返回false。

给定两个链表的头结点head1和head2(注意，另外两个参数adjust0和adjust1用于调整数据,与本题求解无关)。请返回一个bool值代表它们是否相交。

 

 

链接：https://www./courses/1/5/15
来源：牛客网

/*

struct ListNode {

    int val;

    struct ListNode *next;

    ListNode(int x) : val(x), next(NULL) {}

};*/

class ChkIntersection {

public:

    bool chkInter(ListNode* head1, ListNode* head2, int adjust0, int adjust1) {

//如果head1或者head2二者 有一个为空 返回false

        if(head1 == NULL || head2 == NULL)

            return false;

         

//得到head1,head2的环入口点

        ListNode* node1 = check_ring(head1);

        ListNode* node2 = check_ring(head2);

         

        ListNode* iter1 = NULL;

        ListNode* iter2 = NULL;

         

        if(node1 != NULL && node2 != NULL){//表示有环

            if(node1 == node2)

                return true;

            iter1 = node1->next;

            while(iter1 != node1){

                if(iter1 == node2)

                    return true;

                iter1 = iter1->next;

            }

            return false;

        }

        else if(node1 == NULL && node2 == NULL){//代表无环，只是单纯的链表

            iter1 = head1;

            iter2 = head2;

            while(iter1->next != NULL)

                iter1 = iter1->next;

            while(iter2->next != NULL)

                iter2 = iter2->next;

            return iter1 == iter2;

        }

        else

            return false;

    }




private:

// 检查链表是否有环

    ListNode* check_ring(ListNode* head){

        if(head->next == NULL)

            return NULL;

         

        ListNode* fast = head->next->next;

        ListNode* slow = head->next;

        while(fast != NULL && fast != slow){

            fast = fast->next == NULL ? NULL : fast->next->next;

            slow = slow->next;

        }

        if(fast != slow)

            return NULL;

         

        fast = head;

        while(fast != slow){

            fast = fast->next;

            slow = slow->next;

        }

        return fast;

    }

};