数据结构中链表的带环问题

废话不多说直接进入正题

带环问题分两种问法1是判断求是否有环 问法2是要求返回环开始的第一个节点

问法1的处理方式非常的简单 只需要用快慢指针解决即可

思路：定义一个快指针fast 慢指针slow 如果fast能和slow相遇则证明有环 如果不能则无环

struct ListNode *detectCycle(struct ListNode *head) {

    struct ListNode * fast,*slow;
    fast = slow = head;
    while(fast && fast->next)
    {
        fast = fast->next->next;
        slow = slow->next;
        if(fast == slow)
        {
            return true;
        }
    }
    return false;
    
}

关于为什么fast走两步有疑问的请看

fast走2倍课以保证如果有环的话一定会追上slow 因为追及问题时 fast 和 slow 的相对距离每次会缩小1 缩小到0时则一定会追上    如果fast一次走3步或以上的话不一定会追上  例如  假设 slow 进环时 和fast的距离为N 如果fast 一次走三步 则每一次的相对距离会减少2，如果N为奇数的话则第一次追击不会相遇 开始第2次追击时 （设环中的节点数为C）C如果为偶数追击距离为C-1奇数 这种情况会永远都追不上  如果C为奇数C-1为偶数则每次的追击距离缩小2 在距离为0时可以追上

问法2：返回环开始的第一个节点问题 

这类问题有一些的复杂分两种思路

思路1：

定义两个指针一个从相遇节点处开始另一个从头开始他们相遇的位置为环开始的第一个节点

至于为什么是这样是一个数学问题如果大家有兴趣的话可以单独私信我，不感兴趣的话把他当作一个公式就好

struct ListNode *detectCycle(struct ListNode *head) {

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

思路2：

将fast 和slow 节点相遇 位置处分开 变成两条链表相交求焦点的问题

两条链表相交求焦点的问题 思路也比较难想到（ 如果没看懂可以私信我单独解释）先遍历两条链表求出两条链表的长度 求出长度差 再让长链表先走差距步  再让两链表同时开始向后走 （短链表从头开始走）节点的地址相等时 就为两条 链表的焦点（如过到这看懵的话别着急仔细看这段话的思路）

运用以上的思路就可以把环拆分成两条链表的求焦点问题

struct ListNode *detectCycle(struct ListNode *head) {

    struct ListNode * fast,*slow;
    fast = slow = head;
    while(fast && fast->next)
    {
        fast = fast->next->next;
        slow = slow->next;
        if(fast == slow)
        {
            struct ListNode * newhead = fast->next;
            struct ListNode * nh,*h;
            nh = newhead; h = head;
            int numberNH = 0 ,numberH = 0,sum ;
            fast->next = NULL;
            while(nh)
            {
                nh = nh->next;
                numberNH++;
            }
            while(h)
            {
                h = h->next;
                numberH++;
            }
            sum = abs(numberH - numberNH);
            struct ListNode * longlist = newhead;
            struct ListNode * shortlist = head;
            if(numberH>numberNH)
            {
                longlist = head;
                shortlist = newhead;
            }
            while(sum--)
            longlist = longlist->next;
            while(longlist != shortlist)
            {
                longlist = longlist->next;
                shortlist = shortlist->next;
            }
            return longlist;

        }
    }
    return NULL;
    
}

但是这种方法有亿点点复杂不做推荐