10042. LinkedList цикл

Задан связный список. Содержит ли он цикл?

Определение связного списка:

//Java

class ListNode {

int val;

ListNode next;

ListNode(int x) {

val = x;

next = null;

}

}

// C++

class ListNode

{

public:

int val;

ListNode *next;

ListNode(int x) : val(x), next(NULL) {}

};

// C

struct ListNode

{

int val;

struct ListNode* next;

};

Реализуйте функцию hasCycle, которая возвращает 1 если связный список содержит цикл и 0 иначе.

// Java

int hasCycle(ListNode head)

// C, C++

int hasCycle(ListNode *head)

Пример

Функция hasCycle возвращает 0, так как связный список не содержит цикл.

Функция hasCycle возвращает 1, так как связный список содержит цикл.

РЕШЕНИЕ

связный список

Анализ алгоритма

Воспользуемся двумя указателями p и q, двигая их по принципу малого и большого шага. Сначала установим их на начало списка. Далее итеративно двигаем первый указатель p вперед на одну позицию по списку, а второй q – на две позиции. Останавливаемся, если:

· один из указателей (это будет указатель q) достиг конца списка. Тогда список не является циклическим.

· оба указателя указывают на один элемент. Это значит, что быстрый указатель q догнал медленный p, и список содержит цикл.

На третьей итерации указатель q догнал p, оба указателя указывают на вершину со значением 4. Цикл существует.

Реализация алгоритма

int hasCycle(ListNode *head)

{

if (head == NULL) return 0;

Устанавливаем указатели p и q на начало списка.

ListNode* p = head;

ListNode* q = head;

Пока за указателем q имеется хотя бы два элемента (быстрый указатель можно двигать на два шага вперед), продолжаем цикл.

while (q->next && q->next->next)

{

p = p->next;

q = q->next->next;

Если указатели равны, то они указывают на одну и ту же ячейку памяти. Быстрый указатель q догнал медленный p, список содержит цикл.

if (p == q) return 1;

}

Цикла нет, возвращаем 0.

return 0;

}

Java реализация

int hasCycle(ListNode head)

{

if (head == null) return 0;

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 1;

}

return 0;

}