链表（13）----判断链表是否有环，并返回环入口节点

1、链表定义

typedef struct ListElement_t_ {
    void *data;
    struct ListElement_t_ *next;
} ListElement_t;




typedef struct List_t_{
    int size;
    int capacity;
    ListElement_t *head;
    ListElement_t *tail;
} List_t;
           

2、判断链表是否有环，并返回链表入口节点

（1）方法一：根据相遇节点、头结点、入口节点之间的距离关系求解

目的是想看一下，头结点与相遇节点之间的距离和相遇节点与入口节点之间的距离之间的关系

假设链表头结点到入口节点距离为S1， 入口节点一次到相遇节点距离为S2，相遇节点一次遍历到入口节点距离为S3，环长度为L，则L = S2 + S3：

快慢指针第一次相遇时，快指针遍历的节点总数为Fn，慢指针遍历的节点总数为Sn，此时慢指针还没有完成环的一次遍历，而快指针至少完成了环的一次遍历，则慢指针所走距离为：  Sn = S1 + S2，快指针所走距离为：  Fn = S1 + n*L， （n >= 1 )，

列出等式为：

L = S2 + S3

Fn = 2*Sn

Fn = S1 + S2 + n*L

Sn = S1 + S2

==》下面看一下S1和S3之间关系

S1 + S2 + n*L = 2*(S1 + S2)

即：S1 + S2 + n*(S2 + S3) = 2*(S1 + S2)

==>  S1 = n * (S2 + S3) - S2

==>  S1 = n * (S2 + S3) - (S2 + S3) + S3

==>  S1 = (n - 1) * (S2 + S3) + S3

==>  S1 = (n - 1)* L + S3

由于n>=1，所以当从头结点和相遇节点同时出发时，肯定会在入口节点相遇，而且第一个相遇节点必定是入口节点：

ListElement_t *GetEnterNode( List_t *list){
    if( list == NULL || list->head == NULL )
        return NULL;

    ListElement_t *pFast = list->head;
    ListElement_t *pSlow = list->head;
    while( pFast->next != NULL && pFast->next->next != NULL{
        pFast = pFas->next->next;
        pSlow = pSlow->next;
        if( pFast == pSlow)
            break;
    }

//不能使用pFast ！=pSlow，因为如果只有一个节点，此时是相等的
    if( pFast->next == NULL || pFast->next->next == NULL )
        return NULL;

    pSlow = list->head;
    while( pSlow != pFast ){
        pSlow = pSlow->next;
        pFast = pFast->next;
    }

    return pSlow;
}
           

（2）方法二：在相遇节点，按照相交链表的方式求解

其他相关题目下面以超链接形式给出：

链表面试题合集

1、单链表基本操作

2、双链表基本操作

3、循环单链表基本操作

4、反转单链表

5、查找单链表倒数第K个节点

6、倒序打印链表

7、查找链表中间节点

8、删除链表第K个节点，平均时间复杂度为O(1)

9、判断链表是否有环

10、判断两个单链表是否相交

11、求相交链表的第一个相交节点

12、判断是否有环，并判定是6型环还是0型环

13、判断链表是否有环，并求环入口节点

14、合并两个有序单链表

15、给定链表中间某节点，不遍历链表，将带插入节点插入给定节点之前

16、删除链表重复元素