LeetCode 141. Linked List Cycle (Easy)

给定一个链表,确定其中是否有环。

原始问题

https://leetcode.com/problems/linked-list-cycle/

Given a linked list, determine if it has a cycle in it.

Follow up:
Can you solve it without using extra space?

解题思路

最直接的想法是用一个集合将之前出现过的节点保存起来,之后判断新节点是否在已有节点的集合中即可,不过这种方法效率较低,而且需要很大的额外空间,并不是好方法。

这个问题比较优秀的解法是,引入两个指针,一个slow指针一次前进一步,另一个fast指针一次前进两步,这两个指针相遇即是存在环的充要条件。

AC代码

C语言

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
bool hasCycle(struct ListNode *head) {
struct ListNode * slow, * fast;
slow = head;
fast = head;

if (head == NULL) {
return false;
}

while (fast->next != NULL && fast->next->next != NULL) {
slow = slow->next;
fast = fast->next->next;
if (fast == slow)
return true;
}

return false;
}

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class Solution {
public boolean hasCycle(ListNode head) {
ListNode slow, fast;
if (head == null) {
return false;
}

slow = head;
fast = head;

do {
try {
slow = slow.next;
fast = fast.next.next;
} catch(Exception e) {
return false;
}
} while(slow != fast);

return true;
}
}

这里用了一种比较特殊的写法,使用了try...catch...语句块进行异常捕捉,当fast.next.next遇到null时即会发生异常,此时意味着到达了链表结尾,链表中不存在环,故返回false

相关题目

LeetCode 142. Linked List Cycle II (Medium)

LeetCode 160. Intersection of Two Linked Lists (Easy)

文章目录
  1. 1. 原始问题
  2. 2. 解题思路
  3. 3. AC代码
    1. 3.1. C语言
    2. 3.2. Java
  4. 4. 相关题目