相交链表

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

图示两个链表在节点 c1 开始相交：

这道题简单来说就两个思路：

是否相交？
如果是，交点在哪？

我们先来解决第一个问题。

你说的链表，它相交吗？

一说相交，可能有些人的想法是这样的：

它雀食相交，但它不是链表。哪家链表相交节点的next节点有俩的？
我们以示意图为主。

根据图片分析，相交链表从相交节点往后是完全一样的。哪怕是最极端的情况，最后一个节点肯定是共用的，也就是说，我们只要判断两个链表最后一个节点是不是相等即可。

交啊，交在哪啊？

我也不知道啊。
要是这俩链表一样长就好了。
那么有没有办法能让它变得一样长呢？
有，快慢指针。

统计一下链表长度，算出它们的差k。
快指针先走k步。
两个指针一起走，直到指向同一节点。

完成！

代码

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    struct ListNode * head1=headA;
    struct ListNode * head2=headB;
 
    int l1=1;
    int l2=1;
    while(head1->next)
    {
        head1=head1->next;
        ++l1;
    }
    while(head2->next)
    {
        head2=head2->next;
        ++l2;
    }

    if(head1!=head2)
    {
        return NULL;
    }
    
    head1=headB;
    head2=headA;
    if(l1>l2)
    {
        head1=headA;
        head2=headB;
    }

    int k=0;
    if(l1>l2)
    {
        k=l1-l2;
    }
    else
    {
        k=l2-l1;
    }

    while(k--)
    {
        head1=head1->next;
    }
    while(head1&&head2)
    {
        if(head1==head2)
            return head1;
        head1=head1->next;
        head2=head2->next;     
    }
    return NULL;
}

环形链表

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递。仅仅是为了标识链表的实际情况。

如果链表中存在环，则返回 true 。否则，返回 false 。

分析

这道题的解法是快慢指针。

快指针走一步，慢指针走两步。

如果不带环，快指针遍历结束，就返回NULL。
如果带环，当慢指针进入环的时候，每走一次，快慢指针之间的距离会缩小一。总会被追上。

思考题：如果快指针走三步，四步，甚至n步呢？
以三步为例：
我们假设进环时快慢指针距离为n。
那么第一次走距离就是n-2.

如果n为偶数，那么最后距离为0，能够追上。
如果n为奇数，那么最后距离为-1，快指针反超了慢指针，此时两指针的距离是环的长度-1，又要分两种情况：
1. 环的长度-1是偶数，那就可以追上。
2. 是奇数，就永远追不上了。

3倍甚至n倍同理，再说了，三倍的代码哪有二倍的好写，为什么要给自己找事情呢？（瘫）

代码

bool hasCycle(struct ListNode *head) {
    struct ListNode * slow=head;
    struct ListNode * fast=head;
    while(fast&&fast->next)
    {
        slow=slow->next;
        fast=fast->next->next;

        if(slow==fast)
        {
            return true;
        }
    }
    return false;
}

环形链表II

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改链表。

翻译：在上一题的基础上找到入环节点。

分析比啥都重要

假设：

链表头 - 入口点 —— L
入口点- meet —— X
环的长度 —— C

由于不知道环的大小，所以在相遇的时候fast指针可能已经走了N圈，所以fast指针走过的距离：L+N*C+X.
slow走过的距离L+X.

fast的距离是slow的两倍。
可得L+N*C+X=2*(L+X)
化简得L=N*C-X
稍微改一下L=(N-1)*C+C-X

也就是说如果有一个指针从链表头和meet点同时前进的话，它们会在入口点相遇！

写代码吧。

代码

struct ListNode *detectCycle(struct ListNode *head) {
    struct ListNode * slow=head;
    struct ListNode * fast=head;
    while(fast&&fast->next)
    {
        slow=slow->next;
        fast=fast->next->next;

        if(slow==fast)
        {
            struct ListNode * meet=slow;
            while(meet!=head)
            {
                meet=meet->next;
                head=head->next;
            }
            return meet;
        }
    }
    return NULL; //虽然没什么用但是要让编译器知道所有的情况都有返回值
}