两个单链表相交的一系列问题

业务场景：给定两个可能有环也可能无环的单链表，头结点head1和head2,请实现一个函数，如果两个链表相交，请返回链表相交的第一个节点，如果不相交返回null.

构造单链表结构如下：

class ListNode {
public:
    ListNode* next = NULL;
    int value;
    ListNode(int _value) {
        this->value = _value;
    }
};

推断不为空单链表可能存在的样式：

首先判定单链表是否存在环：
思路：利用快慢指针，快指针每次移动两个，慢指针每次移动一个，如存在环结构，当两者相遇之后，快指针返回头部位置，快慢指针每次移动一个，下次相遇的位置，即环相交第一个节点。涉及到数学理论可自行查询。
代码实现：

ListNode* GetListNodeLoop(ListNode* head) {
    if (head == NULL || head->next == NULL ||head->next->next ==NULL) {
        return NULL;
    }

    //快指针每次走两步，慢指针每次走一步
    ListNode* slowPtr= head->next;
    ListNode* quickPtr = head->next->next;

    //如果存在环结构，快慢指针必相遇
    while (quickPtr != slowPtr) {
        if (quickPtr->next == NULL || quickPtr->next->next ==NULL) {
            return NULL;
        }
        quickPtr = quickPtr->next->next;
        slowPtr = slowPtr->next;
    }

    //快慢指针相遇之后，快指针回到起点，慢指针位置不变，快指针每次走两个，慢指针每次走一个，
    quickPtr = head;
    while(quickPtr != slowPtr) {
        quickPtr = quickPtr->next;
        slowPtr = slowPtr->next;
    }
    return quickPtr;
}

推断两个链表可能存在的样式（依据每个节点入度不限，出度为1的原则）

考虑当两个单链表都不存在环，判定两个单链表是否存在重合点（图1，图2）：
思路：分别遍历两个单链表，求最后一个节点指针是否相同，如相等则两个链表必有相交点，图示的第二种情况，则较长的链表，首先循环遍历到两链表等长后，同时遍历，判定第一个相交点。否则最后两个链表节点不相同则为图示的第一种情况。
代码实现：

ListNode* GetBothListNodeLoop(ListNode* head1, ListNode* head2) {
   
    //两个链表如都不存在环结构，判定两个单链表是否相交
    if (head1 == NULL || head2 == NULL) {
        return NULL;
    }
    int n = 0;
    ListNode* node1 = head1;
    ListNode* node2 = head2;
    while (node1->next != NULL) {
        n++;
        node1 = node1->next;
    }
    while (node2->next != NULL) {
        n--;
        node2 = node2->next;
    }
    if (node1 != node2) {
        return NULL;
    }

    //长度较长的链表头节点给node1,短的给node2
    node1 = n > 0 ? head1 : head2;
    node2 = node1 == head1 ? head2 : head1;
    n = std::abs(n);
    while (n > 0) {
        node1 = node1->next;
    }
    while (node1 != node2) {
        node1 = node1->next;
        node2 = node2->next;
    }
    return node1;
}

考虑两个链表都存在环形，则有两种情况，环形节点点相同，环形结点不同（图示4，图示3）。
思路：（1）节点相同，思路与上一致，不过长度范围为头节点到交点位置，先让两链表等长后，同时遍历，则可求出第一个节点位置，（2）节点不同，起始位置从第一个节点的下一个位置开始遍历，如位置与第二个节点位置相同，则返回第一个节点位置即可，否则为NULL

代码实现：

ListNode* bothLoop(ListNode* head1, ListNode* head2, ListNode* loop1, ListNode* loop2) {

    ListNode* cur1 = NULL;
    ListNode* cur2 = NULL;
    if (loop1 == loop2) {
        //结点位置相同，且构成环结构
        int n = 0;
        cur1 = head1, cur2 = head2;
        while (cur1->next != loop1) {
            n++;
            cur1 = cur1->next;
        }
        while (cur2->next != loop2) {
            n--;
            cur2 = cur2->next;
        }
        cur1 = n > 0 ? head1 : head2;
        cur2 = cur1 == head1 ? head2 : head1;
        n = std::abs(n);
        while (n > 0) {
            n--;
            cur1 = cur1->next;
        }
        while (cur1 != cur2) {
            cur1 = cur1->next;
            cur2 = cur2->next;
        }
        return cur1;

    }
    else {
        //存在环，节点位置不相同
        cur1 = loop1->next;
        while (cur1 != loop1)
        {
            if (cur1 == loop2) {
                return cur1;
            }
            cur1 = cur1->next;
        }
        return NULL;
    }
}

总的调度逻辑：

ListNode* getLoopNode(ListNode* head1, ListNode* head2) {

    if (head1 == NULL || head2 == NULL) {
        return NULL;
    }

    ListNode* loop1 = GetListNodeLoop(head1);
    ListNode* loop2 = GetListNodeLoop(head1);

    if (loop1 == NULL && loop2 == NULL) {
        return GetBothListNodeLoop(head1, head2);
    }

    if (loop1 != NULL && loop2 != NULL) {
        return bothLoop(head1, head2, loop1, loop2);
    }
}

以上就是解决此类问题的方法之一。