这是个老套的问题，也是个经典的问题

有没有技术含量，我们不纠结

从最朴实的逻辑思路去分析，然后自己感觉为什么总有人要问及这个问题

...

问题：

• 判断一个单链表是否有环？
• 如果有环存在，找出环的入口节点

要求：

• 空间复杂度为O(1) 也就是不能有额外的存储空间

示意图

image.png

分析

我们最直观的意识，可能就是用set遍历存储节点，由于set不能存储重复元素，所以只要在某个节点存储时，发现set中已经包含元素，则说明有环存在

但是题目要求不能额外开辟空间

剩下的条件很有限，像这样很明确的很简单的条件，往往我们考虑起来却花费很长时间，往往还想不明白，明明感觉很简单的

几何定理也只是通过5条很简单的公理推导出来的

有这种困惑，原因在于我们平时缺乏这方面的思维锻炼

思路方向的诊断

• 首先，判断单链表的状态，一定离不开链表本身的特性，也一定会用到，就是遍历，这点不用怀疑
• 判断环存在，就是在遍历过程中，需要判断是否有重复结点
• 依靠一个遍历指针是做不到的，需要两个指针，才能完成比较
• 判断环，就是两个指针遍历过程中是否相遇，遍历一定次数结束，结束时判断两个指针是否指向同一个节点
• 两个指针要相遇，必然龟兔赛跑绕圈追赶的情形，这就要求两个指针的遍历步长不能是一样的，必然存在一个快，一个慢
• 快指针步长两个节点，慢指针步长1个节点
  • 可否快指针步长3个节点，也不是不可以，但执行代码就稍微麻烦些，每次需要判断next.next是否null

手代替脑活动

情况一：正好在环入口相遇

image.png

情况一：非环入口节点相遇，在环内的一个节点相遇

image.png

• 快指针pf，慢指针ps

• 指针第一次相遇时，快指针遍历过的节点数f, 慢指针遍历过的节点数s

• 慢指针每遍历1个节点，快指针遍历两个结点

  • f = 2s

• 由示意图得知，快指针与慢指针存在绕圈追赶的情形

  • 圈中的节点数: t, 两指针第一次相遇时 绕过的圈数: n
  • 快指针遍历的节点数比 慢指针 快n圈，也就是 多遍历n * t个节点
  • f = s + n * t = 2s
  • 得到 s = n * t; f = 2n * t
  • 两指针相遇时，慢指针遍历的节点 个数 为环中节点数的 n倍，快指针为 2n倍

• 情形一： f = a1 + m1 * t (m1代表 m1圈)

  情形二： f = a2 + m1 * t

• 由情形一 m1 * t + a1，到达环形入口，也就从链表头遍历m1 * t 个节点，在此节点位置再遍历a1个节点，达到入口

  现在就可以得出情形一： a1的长度 就是 环的长度

• 由情形二 m1 * t + a2, 到达相遇节点(环中的一个节点，非入口节点), 也就从链表头遍历m1 * t 个节点，在此节点位置再遍历a2个节点，到达相遇节点

  a2的长度 也等于 环的长度

• 当快指针跟慢指针首次相遇时

  • 让快指针重新指向head，步长为1开始遍历

  • 慢指针从相遇节点开始遍历

  • 这时候 快指针跟慢指针 是同长遍历的，不存在快慢的问题

  • 快指针跟慢指针再次首次相遇时，相遇的节点就是 环的入口节点了

    因为两种情形，绕一圈会在相遇节点再次相遇，但其实，在这之前，有一段遍历是重叠的，就是入口节点到相遇节点这一段

到此，分析结束，实现代码就不存在任何障碍了

实现

struct LinkList {
    int data;
    struct LinkList *next;
};

// 创建 nodeCount个节点的 单链表
struct LinkList* createLinkList(int nodeCount) {
    struct LinkList *head;
    struct LinkList *p;
    for (int i = 0; i < nodeCount; i++) {
        struct LinkList* node = (struct LinkList *)malloc(
sizeof(struct LinkList));
        node->data = i + 1;
        node->next = NULL;
        if (i == 0) {
            head = node;
            p = node;
        } else {
            p->next = node;
            p = node;
        }
    }
    return head;
}

// 打印单链表
// 最多打印 maxNodeCount 个节点
void printLinkList(struct LinkList *linkList, int maxNodeCount) {
    int index = 0;
    struct LinkList *p = linkList;
    if (p == NULL) {
        return;
    }
    while (p != NULL) {
        if (index >= maxNodeCount) {
            break;
        }
        printf("-->%i", p->data);
        p = p->next;
        index++;
    }
    

    printf("\n");
}

// 单链表构建一个环
// nodeIndex 第nodeIndex个节点 作为环入口
void configLinkCircle(struct LinkList *linkList, int nodeIndex) {
    int index = 0;
    struct LinkList *entraceNode = NULL;
    struct LinkList *p = linkList;
    if (p == NULL) {
        return;
    }
    while (p != NULL) {
        if (index == nodeIndex) {
            entraceNode = p;
        }
        if (p->next == NULL) {
            p->next = entraceNode;
            break;
        }
        p = p->next;
        index++;
    }
}

// 判断环 返回入口节点
struct LinkList *checkLinkListCircle(struct LinkList *linkList) {
    // 链表头
    struct LinkList *head = linkList;
    // 快指针
    struct LinkList *pf = linkList;
    // 慢指针
    struct LinkList *ps = linkList;
    if (linkList == NULL) {
        return NULL;
    }
    
    while (true) {
        if (pf != NULL && pf->next != NULL) {
            ps = ps->next;
            pf = pf->next->next;
            if (pf == ps) {
                break;
            }
        } else {
            printf("\n链表不存在环\n");
            return NULL;
        }
    }
    
    pf = head;
    int index = 0;
    while (pf != ps) {
        index++;
        ps = ps->next;
        pf = pf->next;
    }
    index++;
    printf("\n链表在第%i个节点处形成环，节点为：%i\n", index + 1, pf->data);
    
    return NULL;
}


int main(int argc, const char * argv[]) {
    int n = 30;
    
    int nodeCount = 20;
    struct LinkList *linkList = createLinkList(nodeCount);
    configLinkCircle(linkList, 8);
    printLinkList(linkList, nodeCount * 2);
    
    struct LinkList* entraceNode = checkLinkListCircle(linkList);
    
    return 0;
}

• 单链表是否存在环的问题一点也不复杂，但往往让人困惑的地方在于简单的数学公式推导，靠脑子抽象往往不会任何输出