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

问题

单链表可能有环，也可能无环。给定两个单链表的头节点head1和head2，这两个链表可能相交，也可能不相交。请实现一个函数，如果两个链表相交，请返回相交的第一个节点；如果不相交，返回null即可。

要求：
如果链表1的长度为 N，链表2的长度为 M，时间复杂度达到O( N+M)，额外空 间复杂度请达到O(1)。

思路

两条单链表的相交情况

情况一： a链表有环，b链表无环

情况二： a链表无环，b链表无环

情况三： a链表有环，b链表有环

由链表本身的特点可得，情况一两链表是不可能相交的。故我们只需讨论情况二与情况三下面链表相交的形式。那么首先要解决的问题是，判断链表是否有环，根据两链表的有环情况调用相应的处理函数。

得到第一个相交节点的主函数

Node *getIntersectNode(Node *head1, Node *head2)
{
    if (head1 == NULL || head2 == NULL)
    {
        return NULL;
    }
    Node *loop1 = getLoopNode(head1);
    Node *loop2 = getLoopNode(head2);
    if (loop1 == NULL && loop2 == NULL)
    {
        return noLoop(head1, head2);
    }
    if (loop1 != NULL && loop2 != NULL) 
    {
        return bothLoop(head1, loop1, head2, loop2);
    }
    return NULL;
}

返回入环节点

有两种策略可以得到链表的入环节点，分别是hash表和快慢指针。使用hash表的实现比较简单，我们只需将遍历的节点用map保存起来。在访问下一个节点之前，先查询是否已保存，若map中已存在该节点，那么此节点为入环节点将它返回即可。

下面简单地介绍一下，使用快慢指针如何得到入环节点。已知，在有环链表中，使用快慢指针从头节点开始出发，一定会相遇于某个节点node1。现将node1与head两节点同时向下遍历，两节点第一次相遇的节点即为第一个入环节点。
这是一个小结论，很容易用数学证明，就不再此处展开。

代码如下：

Node *getLoopNode(Node *head)
{
    //边界条件的判定
    if (head == NULL || head->next == NULL || head->next->next == NULL)
    {
        return NULL;
    }

    Node* n1 = head->next; // n1 -> slow
    Node* n2 = head->next->next; // n2 -> fast
    while (n1 != n2)
    {
        //指针使用前，必须判空
        if (n2->next == NULL || n2->next->next == NULL)
        {
            return NULL;
        }
        n2 = n2->next->next;
        n1 = n1->next;
    }
    n2 = head; // n2 -> walk again from head
    //相遇处节点与head节点同时向下遍历，有环则必定相遇于入环节点
    while (n1 != n2)
    {
        //有环链表，此处无需判空
        n1 = n1->next;
        n2 = n2->next;
    }
    return n1;
}

两无环链表

两无环链表有两种拓扑结构
两链表平行
两链表相交（呈Y型）

两链表相交为什么不能呈X型，原因很简单。hint：仍是链表的结构特点所决定的

Node* noLoop(Node* head1, Node* head2)
{
    if (head1 == NULL || head2 == NULL)
    {
        return NULL;
    }
    Node *cur1 = head1;
    Node *cur2 = head2;
    int n = 0;

    //next非空时，继续向下遍历，直到遍历结尾
    while (cur1->next != NULL)
    {
        n++;
        cur1 = cur1->next;
    }
    while (cur2->next != NULL)
    {
        n--;
        cur2 = cur2->next;
    }
    if (cur1 != cur2)
    {
        return NULL;
    }
    //长链表为cur1，短链表为cur2，n为两链表长度差
    cur1 = n > 0 ? head1 : head2;
    cur2 = cur1 == head1 ? head2 : head1;
    n = abs(n);

    //长链表先走n步长
    while (n != 0)
    {
        n--;
        cur1 = cur1->next;
    }

    while (cur1 != cur2)
    {
        if (cur1 == NULL || cur2 == NULL)
        {
            return NULL;
        }
        cur1 = cur1->next;
        cur2 = cur2->next;
    }
    return cur1;
}

两有环链表

具体实现见代码注释，清晰明了。有一个地方值得注意的是，当两入环节点不同时，返回两个node其中任一一个都行。理解的方式不同而已，都可以当作第一个相交节点。

Node *bothLoop(Node *head1, Node *loop1, Node *head2, Node *loop2)
{
    Node *cur1 = NULL;
    Node *cur2 = NULL;

    //两入环节点相同，两链表在“入环处以上”相交
    //处理方式类似于两无环链表，不同的是，遍历到入环节点处终止
    if (loop1 == loop2)
    {
        cur1 = head1;
        cur2 = head2;
        int n = 0;

        while (cur1 != loop1)
        {
            n++;
            cur1 = cur1->next;
        }
        while (cur2 != loop2)
        {
            n--;
            cur2 = cur2->next;
        }
        cur1 = n > 0 ? head1 : head2;
        cur2 = cur1 == head1 ? head2 : head1;
        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 loop1;
            }
            cur1 = cur1->next;
        }
        return NULL;
    }
}