链表-链表有环问题

1. 判断一个单向链表是否有环

有环的链链表大概张这样

有环的链表和普通的链表的区别就是尾指针指向了链表中的某一个节点，这会导致我们在遍历链表的时候无法遍历完毕，因为链表中不存在尾指针了，最终会无线循环在链表的环状结构上。
钟表我们都知道，时针和分针的速度不同但是两个指针总会相遇，判断一个链表是否有环我们也可以使用两个指针p，q，p指针的每次的步长为两个节点，q指针的步长为一个节点。如果链表中存在环状结构，那么这两个指针就一定会相遇，如果不存在环状结构，p指针就一定会走到链表的尽头。

code

如果链表有环，返回环中的其中一个节点，如果无环，返回NULL

ElemSN* judgeListHaveCircle(ElemSN *head){
    if(NULL==head){
        return NULL;
    }
    ElemSN *p=head,*q=head;
    while(p!=NULL&&p!=q){
        if(p->next!=NULL&&p->next->next!=NULL){
            p=p->next->next;
        }else{
            return NULL;
        }
        q=q->next;
    }
    return p;
}

2. 链表有环，找到链表的入口节点

1. 先找到环中的任意一个节点p,然后q绕着环走一圈用于计算环的节点个数n,
2. 两个指针链表的头部开始，一个指针先走n个节点，然后另一个指针再走，两个指针相遇时，即为环的入口节点

code

node 参数为链表环中的任意一个节点，即上面那个函数计算的节点地址。

ElemSN* getCircleListStartNode(ElemSN *head,ElemSN *node){
    if(head==NULL||node==NULL){
        return NULL;
    }
    ElemSN *p=node,*q=node;
    int n=1;
    do{
        q=q->next;
        n++;
    }while(p!=q);
    p=q=head;
    while (n) {
        n--;
        p=p->next;
    }
    while (p!=q) {
        p=p->next;
        q=q->next;
    }
    return p;
}