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

在本题中，单链表可能有环，也可能无环。给定两个 单链表的头节点 head1和head2，这两个链表可能相交，也可能 不相交。请实现一个函数， 如果两个链表相交，请返回相交的 第一个节点；如果不相交，返回null 即可。
要求：如果链表1 的长度为N，链表2的长度为M，时间复杂度请达到 O(N+M)，额外 空间复杂度请达到O(1)。
题目来自 左程云 《程序员代码面试指南》

分析：

从链表有没有环来说，可以分为三种情况：
1）两个链表均为单链表，无环；
2）两个链表，1个有环，一个无环；
3）两个链表全有环。
下面从这三种情况分别分析。

1）两个链表均为单链表，无环

如果两个链表长度相同，那么如果两个链表的某个结点相等，那么返回该结点即可。如果不等，同时next。
但是两个链表长度可能会不一样。这时可以先获取两个链表的长度，让长链表先走长度差那么多步，这时两个链表长度也就相等了。

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        int numA=0,numB=0;
        ListNode *pa=headA,*pb=headB;
        while(pa!=NULL&&pb!=NULL)  //两个同时走，直到一个为空
        {
            pa=pa->next;
            pb=pb->next;
            ++numA;
            ++numB;
        }
        while(pa!=NULL)  //这个和下面的while，两个只能发生一个
        {
            pa=pa->next;
            ++numA;
        }
        while(pb!=NULL)
        {
            pb=pb->next;
            ++numB;
        }
        pa=headA;
        pb=headB;
        if(numA>numB)  //A长
        {
            while(numA-numB)  //A先走
            {
                pa=pa->next;
                --numA;
            }
        }
        else  //B长
        {
            while(numB-numA)  //B先走
            {
                pb=pb->next;
                --numB;
            }
        }
        while(pa!=NULL&&pb!=NULL) //两个同时走
        {
            if(pa==pb)
                return pa;
            else
            {
                pa=pa->next;
                pb=pb->next;
            }
        }
        return NULL;
    }
};

2）两个链表，1个有环，一个无环

这种情况是不可能相交的，...

3）两个链表全有环。

1. 全有环但是不相交
   这种情况就是两个链表各自成环，那么可以链表A结点处在环的入口处，另链表B从环入口结点处一直走环，如果转了一圈，还没有遇到A的结点，那么就说明两个链表不相交。
2. 全有环，相交意味着环是一样的，一种情况是在进入环之前两个链表已经相交。
   那么这个时候第一个相交的结点不在环里面。此时，可以想象将两个链表从头部截断到各自的环的入口处，那么就化解成，两个单链表找第一个相交的结点了。
3. 全有环，相交意味着环是一样的，另一种情况是在两个链表进入环的入口不同。
   此时返回任一个应该都正确。可以同样通过A不动，B转一圈，遇到A就说明相交了。

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode *fast=head;
        ListNode *slow=head;
        bool hasCycle=false;
        while(fast!=NULL&&fast->next!=NULL)
        {
            slow=slow->next;
            fast=fast->next->next;
            if(slow==fast)
            {
                hasCycle=true;
                break;
            }
        }
        slow=head;
        while(hasCycle)
        {
            if(slow!=fast)
            {
                slow=slow->next;
                fast=fast->next;
            }
            else
                return slow;
        }
        return NULL;
    }
};
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode * firAcycle=detectCycle(headA);
        ListNode * firBcycle=detectCycle(headB);
        if(firAcycle==firBcycle) //说明两个环入口一样，第二种情况
        {
            //转换成 第一种无环相交 不过这次 尾结点不是 NULL，而是 firAcycle 和 firBcycle
        }
        else // 可能不相交 也可能两个环的入口不一样
        {
        ListNode *tmp=firAcycle->next;
        while(tmp!=firAcycle)
        {
            if(tmp==firBcycle) //第三种情况 相交 环入口不一样
                return firBcycle;
            tmp=tmp->next;
        }
        return false; //不相交
        }
    }
// 有环的话返回入口结点，无环返回NULL
    ListNode *detectCycle(ListNode *head) {
        ListNode *fast=head; //快慢双指针
        ListNode *slow=head;
        bool hasCycle=false;
        while(fast!=NULL&&fast->next!=NULL)
        {
            slow=slow->next;
            fast=fast->next->next;
            if(slow==fast)  //相等有环 记录相遇结点
            {
                hasCycle=true;
                break;
            }
        }
        slow=head;
        while(hasCycle)
        {
            if(slow!=fast)
            {
                slow=slow->next;
                fast=fast->next;
            }
            else
                return slow;
        }
        return NULL;
    }
};

注意，这只是把这个问题分成这三种情况，实际种要把这三种写到一个主函数，可以把一些代码封装成函数，方便复用。