导航
导航
文章目录
  1. 题目
  2. 翻译

LeetCode-141.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?

翻译

给出一个链表,判断它是否有环。
跟进:你能不适用额外空间解决本题吗?

设立快慢指针,快指针每次走一步,慢指针每次走两步。如果快指针走到了链表尾则无环,如果快慢指针相遇则有环:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public boolean hasCycle(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) return true;
}
return false;
}
}