Given a linked list,
determine if it has a cycle in it.
Follow up:
Can you solve it without
using extra space?
Задан связный список.
Определить, содержит ли он цикл.
Решите задачу с константной
памятью.
// C++
/**
*
Definition for singly-linked list.
* struct
ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
bool hasCycle(ListNode *head) {
}
};
// Java
/**
*
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) {
}
}
список
Воспользуемся двумя
указателями, двигая их по принципу малого и большого шага. Сначала установим их
на начало списка. Далее итеративно двигаем первый указатель вперед на одну
позицию по списку, а второй – на две позиции. Останавливаемся, если:
·
один из указателей достиг конца списка. Тогда список не
является циклическим.
·
оба указателя указывают на один элемент. Это значит, что
быстрый указатель догнал медленный, и список содержит цикл.
Реализация алгоритма
class Solution
{
public:
bool hasCycle(ListNode *head)
{
Если указатель на голову head
равен NULL, то цикла нет.
if (!head) return false;
Объявим медленный p и быстрый q указатели.
ListNode* p = head;
ListNode* q = head;
Двигаемся пока быстрый указатель q
не достигнет конца списка.
while(q->next
&& q->next->next)
{
p = p->next;
q =
q->next->next;
Если быстрый указатель догнал медленный, то список содержит цикл.
if (p == q) return true;
}
Если указатель q достиг конца
списка, то цикла в нем нет.
return false;
}
};
Java реализация
class Solution
{
public boolean hasCycle(ListNode head)
{
if (head == null) return
false;
ListNode p = head;
ListNode q = head;
while(q.next != null && q.next.next != null)
{
p = p.next;
q = q.next.next;
if (p == q) return true;
}
return false;
}
}