经典的带环链表问题(链表补充）_数据结构

环形链表1

运用快慢指针的方法，fast ,slow从头节点出发，快指针走两步，慢指针走一步，若有环，快指针先进环，后续如果慢指针和快指针相遇，则链表带环。转换成了追击问题。

struct listnode {
    int val;
    struct listnode *next;
};

 typedef struct listnode ln;
bool hascycle(struct listnode *head) {
    ln*slow,*fast;
    slow=fast=head;
    while(fast && fast->next){
       slow=slow->next;
       fast=fast->next->next;
       if(slow==fast)
       return true;
}
       return false;
}

思考：为什么一定会相遇，会不会错过，永远追不上？若快指针走三步，四步呢？

证明：假设链表就是有环，slow（1步）进环时，fast（两步）与slow的距离为n,追击过程中，每走一次，n都会-1，最后到0。本题的思想证明，距离为0就是追上了。

若fast走三步，同样假设slow进环时，fast与slow相差n,

fast追击slow过程中，距离变化一直-2,但是最后结果要注意，n为偶数时，最后变为0，n为奇数时，最后为-1.而当距离为-1时，两指针会错过，进行新一轮追击。这时假设环的长度为c。新的距离就变成c-1了，这是又要将c分为奇数，偶数进行讨论。

那么是否存在n是奇数且c是偶数的情况呢，

假设从出发位置到进环的位置相差l，slow进环时，fast已经走了x圈，且fast与slow相差n:

进环时：slow走的距离->l

fast走的距离->l+x*c+c-n

fast的距离应该为slow的三倍:3*l=l+x*c+c-n

化简为：2*l=(x+1)*c-n 若要满足该等式，若c是偶数,n必须是偶数。若n是奇数,如果c是偶数，则（x+1）*偶数一定是偶数，偶数-奇数！=偶数。

所以上述条件不成立，故永远追不上的条件不成立。

结论：一定能追上。

n是偶数第一轮追上。n是奇数第一轮追不上，c是奇数，第二轮追上。

其他走四步等的条件证明过程类似。

环形链表2

证明过程如下：

struct listnode {
   int val;
  struct listnode *next;
 };
 
typedef struct  listnode ln;
struct listnode *detectcycle(struct listnode *head) {
    ln*slow,*fast,*meet;
    slow=fast=head;
    while(fast && fast->next){
        slow=slow->next;
        fast=fast->next->next;
        if(slow==fast){
            meet=slow;
            while(meet!=head){
                meet=meet->next;
                head=head->next;
            }
            return meet;
        }
         
    }
    return null;
}

这种方法不容易想到，还有另外一种方法，将快慢指针相遇点newhead=meet->next,meet->next=null,此时从newhead开始，与原链表head通过相交链表的思路求解。

struct listnode {
    int val;
   struct listnode *next;
 };

 typedef struct  listnode ln;
 struct listnode *getintersectionnode(struct listnode *heada, struct listnode *headb) {
    ln*cur1=heada,*cur2=headb;
    int lena=1,lenb=1;
    while(cur1){
        cur1=cur1->next;
        lena++;
    }
    while(cur2){
        cur2=cur2->next;
        lenb++;
    }
    //尾节点不相同就没有相交
    if(cur1!=cur2){
    return null;
    }
    //假设法
    int gap=abs(lena-lenb);
    ln* longlist = heada;
    ln* shortlist = headb;
    if(lena<lenb){
        longlist=headb;
        shortlist=heada;
    }
    while(gap--){
     longlist=longlist->next;
    }
    while(longlist!=shortlist){
        longlist=longlist->next;
        shortlist=shortlist->next;
    }
    return longlist; 
}
struct listnode *detectcycle(struct listnode *head) {
    ln*slow,*fast,*meet;
    slow=fast=head;
    while(fast && fast->next){
        slow=slow->next;
        fast=fast->next->next;
        if(slow==fast){
        meet=slow;
        ln* newhead=meet->next;
        meet->next=null;
        return getintersectionnode(head,newhead);  
        }                
}
return null;
   
}