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

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

喜欢就点在看哦~

我来评几句
登录后评论

已发表评论数()

相关站点

+订阅
热门文章