leetcode--环形链表，以及快慢指针详细讲解（C语言）

题目：给一个链表的表头head，编写程序去判断是否存在环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。

为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。

注意：pos 不作为参数进行传递 。

仅仅是为了标识链表的实际情况。

如果链表中存在环，返回true，反之返回false。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/linked-list-cycle

栗子：

输入：head=[1,3,4,2];pos=1

输出：true

输入：head=[1,3,4,2],pos=-1

输出：false

 输入：head=[1];pos=-1

输出：false

接下来就是交给大家的时间了，先尝试做一下。

完成下面函数

/**

 * Definition for singly-linked list.

 * struct ListNode {

 *     int val;

 *     struct ListNode *next;

 * };

 */

bool hasCycle(struct ListNode *head) {

}

 

方案1：快慢指针

快慢指针在链表中时常会被用到，因为就像是表中的分针和秒针一样，总会相遇的。

题目是判断是否存在环，如果存在的话，必然有结点会重复出现。

快指针走两步，慢指针走一步，如果相遇就说明存在着环，不相遇说明不存在。

或许有些同学不理解快慢指针的真正意义，发现走快指针走三步，慢指针走一步，或者快指针走4步，慢指针走一步，再或者快指针走3步，慢指针走2步等等都是可以完成题目的要求，而不知道这样走法是代表什么意思。

快指针走2步，慢指针走1步：假设快慢指针都只走一次，也就是快指针指向2，慢指针指向1，此时的慢指针就是快指针的一半；假设快慢指针都走两次，此时的快指针走到4，慢指针走到2，依然是一半的关系。

从这里可以得出，快指针走2步慢指针走1步，最后慢指针就是指向整个链表的中间位置，快指针是指向链表的尾部位置。

判断回文串可用到。

快指针走3步，慢指针走1步：分析的原理跟上面一样，假设快慢指针都只走一次，此时快指针指向3，慢指针指向1，相当于慢指针是快指针的三分之一；假设快慢指针都走两次，结果还是一样的，当快指针指向链表的尾部时，慢指针指向整个链表的三分之一处。

依次类推，如果给你一个单链表，在O(n)和O(1)的情况下去找到链表的四分之一处的结点，那么使用快慢指针，快指针走4步，慢指针走1步即可达到，慢指针就是指向整个链表的四分之一处的结点指针。

 

这下大家应该明白了快慢指针的真正意思了吧。

方案2：哈希表法

  相信有很多小伙伴看到重复出现的题目时，会想到用哈希表来实现吧，利用哈希表来实现的思想就是输入结点，查找该结点在哈希表是否存在，如果存在说明该链表有环，不存在直接加入哈希表中，一直循环....