LeetCode 141：环形链表
这次来写一下 LeetCode 的第 141 题，环形链表。
题目描述
题目直接从 LeetCode 上截图过来，题目如下：
上面的题就是 环形链表 题目的截图，同时 LeetCode 给出了一个函数的定义，然后要求实现 环形链表 的函数体。函数定义如下：
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ bool hasCycle(struct ListNode *head) { }
从上面的定义可以看出，是一个单链表。单链表只能顺着节点的指针依次找下去，而不能往回找。
问题分析
这个题目是要判断链表中是否存在环，从题目的图中可以看出，链表的最后一个节点的指针可能会指回它前面的某个节点，从而使链表形成一个环。那到链表中是否存在环，需要程序进行判断。
首先说说没有环的情况，没有环的情况是比较简单的，就是正常的遍历链表，只要链表的某个节点的 next 指针指向了 NULL，那么就说明到达链表的结尾，也就不存在环了。但是，问题既然这样给出了，那么判断链表是否有环才是关键。
关于判断链表是否有环这个问题可以有两种解决方法。
第一种方法是把所经过的每个节点的地址记录下来，然后每次移动指针后判断当前地址是否被记录过，如果记录过，则说明该链表是个环。如下图所示。
上面图中，当前指针指向第一个链表节点，那么就把当前节点的地址记录在地址列表中。然后当 cur 指针依次经过 0x0002、0x0003 和 0x0004 指针后情况是如下图所示。
经过这么一轮的遍历下来，我们已经可以用人眼看出来，已经到了最后一个节点，再遍历下去就形成环了。当指针 cur 指向地址 0x0002 时，这个地址在 地址列表 中是可以找到的，那么就说明该链表是有环的。
这种方法要使用另外一种数据结构，然后通过查表的方法来判断链表是否有环。这样的方式会增加额外的空间。
另一种方式是通过 快慢指针 来判断链表中是否存在环。首先需要定义两个指针，一个快指针（fast）和一个慢指针（slow），快指针每次跳一个节点进行链表的遍历，慢指针则逐个节点进行遍历。在链表中有环的情况下，快指针和慢指针是会相遇的。想想钟表的时针和分针分别一快一慢的前进着，然后还会经常相遇，因为钟表是个环。看下图。
通过上面的图可以看出，通过 快慢指针 可以判断出链表是否有环。
代码实现
判断链表是否有环，我在实现时使用了第二种方法，因为第一种方式需要使用另外的数据结构进行记录并查表。而 快慢指针 这种方式显得简单粗暴。虽然上面又是解释又是画图，其实代码反倒不多，代码如下：
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ bool hasCycle(struct ListNode *head) { if (!head) { return false; }
struct ListNode *fast = head->next; struct ListNode *slow = head;
while (slow && fast && fast->next) { if (slow == fast) { return true; }
slow = slow->next; fast = fast->next->next; }
return false; }
代码不需要进行注释，因为已经很简单了。
提交结果
在写完 hasCycle 函数体后，点击右下角的 “
执行代码
”，然后观察
“输出” 和 “预期结果”
是否一致，一致的话就点击 “
提交
” 按钮。点击 “提交” 按钮后，系统会使用更多的测试用例来测试我们写的函数体，
如果所有的测试用例都通过了，那么就会给出 “通过” 的字样，
如果没有通过，会给出失败的那一组测试用例，我们继续修改代码
。我们以上代码 “提交” 以后的截图如下：
这个题目感觉没有坑在里面，还是比较容易完成的。
喜欢就点在看哦~
About The Author
