LeetCode 141：环形链表

LeetCode 相关的文章：

1、 LeetCode | 206.反转链表

2、 LeetCode | 24.两两交换链表中的节点

这次来写一下 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 函数体后，点击右下角的 “ 执行代码 ”，然后观察  “输出” 和 “预期结果”  是否一致，一致的话就点击 “ 提交 ” 按钮。点击 “提交” 按钮后，系统会使用更多的测试用例来测试我们写的函数体， 如果所有的测试用例都通过了，那么就会给出 “通过” 的字样， 如果没有通过，会给出失败的那一组测试用例，我们继续修改代码 。我们以上代码 “提交” 以后的截图如下：

这个题目感觉没有坑在里面，还是比较容易完成的。

喜欢就点在看哦~