链表与环

题目1：给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。（源于牛客网剑指offer）

1、设置快慢指针，假如有环，他们最后一定相遇。
2、两个指针分别从链表头和相遇点继续出发，每次走一步，最后一定相遇于环入口。

代码：

struct ListNode 
{
    int val;
    struct ListNode* next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
ListNode* EntryNodeOfLoop(ListNode* pHead)
{
    //0个结点
    if (pHead == NULL)
        return NULL;
    //1个结点
    if (pHead->next == pHead)
        return pHead;
    //多个结点
    //1、设置快慢指针，假如有环，他们最后一定相遇。
    ListNode* slow = pHead;
    ListNode* fast = pHead;

    ListNode* meet = NULL;
    while (1)
    {
        if (fast->next != NULL)
            fast = fast->next; //fast的第一步
        else
            return NULL;
        if (fast->next != NULL)
            fast = fast->next;//fast的第二步
        else
            return NULL;

        slow = slow->next;

        if (slow == fast)
        {
            meet = slow;
            break;
        }
    }

    //2、两个指针分别从链表头和相遇点继续出发，每次走一步，最后一定相遇于环入口。
    ListNode* p1 = pHead;
    ListNode* p2 = meet;
    while (1)
    {
        if (p1 == p2)
            return p1;
        p1 = p1->next;
        p2 = p2->next;
    }
}

题目2：给2个链表判断是否相交，相交求交点，顺序/逆序打印相交部分

是否相交：判断最后一个节点是否相同
顺序：分别压入两个队列。先把两个链表弄成长度相同的（长链表扔一部分），然后依次比较队列头，不相同扔掉，相同打印。
逆序：分别压入两个栈。依次比较栈顶，相同打印。