环形链表的经典问题

环形链表

环形链表的介绍
链表中是否带环
返回链表开始入环的第一个节点

本文主要介绍如何判断一个链表是否是环形链表，以及如何得到环形链表中的第一个节点。

环形链表的介绍

环形链表是一种链表数据结构，环形链表是某个节点的next指针指向前面的节点或指向自己这个节点的一个链表，这个链表就构成了环形链表。

链表中是否带环

要判断一个链表中是否带环，首先直接给出结论，我们可以用一个快指针（一次走两步），应该慢指针（一次走一步），如果该链表带环，最后快指针和慢指针就会在环中相遇，否则就是快指针走到空，这就表明该链表不带环。
判断一个链表是否带环Leetcode

根据这个思想，可以写出以下代码（快指针走两步，慢指针走一步）：

bool hasCycle(struct ListNode *head) 
{
    if(head==NULL)
        return false;
    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;
}

分析:当链表为带环链表时，为什么快指针走两步，慢指针走一步就一定会在环中相遇?

当为环形链表时，快慢指针最总都会进入到环内。
假设这个环是顺时针方向走的，当slow进入到带环的第一个节点，此时slow距离fast的节点个数为N，这个环的大小为C，示意图如上所示。fast走2步，slow走一步，那么两者之间的距离就会变成N-1，继续走就会变成N-2,N-3…,1,0.当两者之间的节点个数变为0那么就表示两者相遇了，这也可说明这个链表是带环的。所以当快指针走一步慢指针走两步（带环的链表），那么它们一定会在环中相遇。

如果快指针走三步，慢指针还是走一步那么它们是否还会再环中相遇吗？结论是它们也一定会在环中相遇。

假设这个环是顺时针方向走的，当slow进入到带环的第一个节点，此时slow距离fast的节点个数为N，这个环的大小为C，示意图如上所示。第一次fast走三步，slow走两步，这时两者之间的距离为N-2，继续走依次次为N-4…，当N为偶数是N-6,…,4,2,0。此时两者必定会在环中相遇。
当N为奇数时，两者之间的距离依次为N-6,…,5,3,1,-1。当为-1时表示fast追过了，其示意图如下：
这就表示进行到了新一轮的追击中了，此时fast距离slow相差C-1个节点（从顺时针方向看），当C为奇数那么C-1就是偶数，那么距离的变化一定是C-3,…,4,2,0。所以此时一定也能相遇。
当C为偶数时，那就表示追不上，但是不存在这个情况（同时C为偶数并且N为奇数）。分析如下：

首先假设slow进环前走的距离为L，那么fast所走的距离为L+xC+C-N，其中x表示在环形链表中所转的圈数。又由于fast所走的距离为slow的三倍，所以有等式L+xC+C-N=3L,所以就有2L=(x+1)*C-N。左边等式一定是偶数，则右边也一定为偶数，假设C为偶数那么则N一定也是偶数，不然就不满足左边是偶数右边不是偶数了。只有当N为奇数，C为偶数才会永远无法再环中相遇，但这种情况不存在。 所以这也表示当fast走三步，slow走一步也一定会在环中相遇。

返回链表开始入环的第一个节点

返回链表开始入环的第一个节点Leetcode
使用快慢指针，快指针走两步慢指针走一步，它们两个一定会在环中相遇。此时一个从相遇点走，另一个从头节点开始走，两者同时走，当两者相遇时，这个相遇的节点就是入环的第一个节点。
根据这个思路代码如下：

struct ListNode *detectCycle(struct ListNode *head) 
{
    struct ListNode *slow=head;
    struct ListNode *fast=head;
    if(fast==NULL||fast->next==NULL)
        return NULL;
    struct ListNode *ret=NULL;
    while(fast&&fast->next)
    {
        slow=slow->next;
        fast=fast->next->next;
        if(slow==fast)
        {
            ret=slow;
            break;
        }
    }
    if(!fast||!fast->next)
        return NULL;
    struct ListNode *cur=head;
    while(cur)
    {
        if(cur==ret)
            return ret;
        cur=cur->next;
        ret=ret->next;
    }
    return NULL;
}

在这里插入图片描述

为什么一个从相遇点走，应该从头节点走，两者相遇的点就是环形链表环形的入口节点？

ret表示入环的第一个节点，meet表示快慢指针相遇点，head表示链表的头节点。环的大小为C，其示意图如上所示。慢指针到两者相遇所走的距离为L+C-N，快指针在两者相遇所走的距离为L+xC+C-N,由于快指针每次走两步，慢指针每次走一步，所以就有这个关系：2*(L+C-N)=L+xC+C-N,所以就有L=(x-1)C+N,其中x一定大于1。相遇点meet到环形入口节点的距离是N，而头节点到环形链表的入口节点距离是L，所以一个从相遇的节点开始走，另一个节点从头节点开始走，两者一定会在环形链表的入口节点相遇。

另一个思路就是通过寻找链表相交的第一个节点的思路：
依旧是通过快慢指针找到相遇点，再将相遇节点的next置空。这就相当于找链表第一个相交的节点了。
代码如下：

//找两个相交的链表
 struct ListNode *firstcrossnode(struct ListNode *head1,struct ListNode *head2) 
 {
    if(head1==NULL)
        return NULL;
    if(head2==NULL)
        return NULL;
    int len1=0;
    int len2=0;
    struct ListNode *cur1=head1;
    struct ListNode *cur2=head2;
    while(cur1)
    {
        cur1=cur1->next;
        len1++;
    }
    while(cur2)
    {
        cur2=cur2->next;
        len2++;
    }
    int len=abs(len1-len2);
    struct ListNode *longlist=head1;
    struct ListNode *shortlist=head2;
    if(len1<len2)
    {
        longlist=head2;
        shortlist=head1;
    }
    while(len--)
    {
        longlist=longlist->next;
    }
    while(longlist)
    {
        if(longlist==shortlist)
            return longlist;
        longlist=longlist->next;
        shortlist=shortlist->next;
    }
    return NULL;
 }
struct ListNode *detectCycle(struct ListNode *head) 
{
    struct ListNode *slow=head;
    struct ListNode *fast=head;
    if(fast==NULL||fast->next==NULL)
        return NULL;
    struct ListNode *meet=NULL;
    while(fast&&fast->next)
    {
        slow=slow->next;
        fast=fast->next->next;
        if(slow==fast)
        {
            meet=slow;
            break;
        }
    }
    if(!fast||!fast->next)
        return NULL;
    struct ListNode*newhead=meet->next;
    meet->next=NULL;//将环形链表切割开
    struct ListNode* cur=head;
    //找第一个相交的链表
    struct ListNode*ret=firstcrossnode(cur,newhead);
    meet->next=newhead;//将链表还原回去
    return ret;
}