10043. LinkedList Цикл точка входа

Задан связный список. Верните указатель на вершину, в которой начинается цикл. Если цикла нет, верните null.

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

//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) {}

};

Реализуйте функцию detectCycle, которая возвращает указатель на вершину, в которой начинается цикл. Если цикла нет, то верните null.

// Java

ListNode detectCycle(ListNode head)

// C++

ListNode* detectCycle(ListNode *head)

Пример

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

Функция detectCycle возвращает указатель на вершину со значением 3 – точку входа в цикл.

РЕШЕНИЕ

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

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

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

Пусть расстояние от начала до вершины, в которой начинается цикл, равно x. Расстояние от начала цикла до точки встречи двух указателей равно y. Расстояние от вершины, на которую указывает p, до начала цикла по ходу списка равно z.

Предположим, что указатели встретились так, что быстрый прошел только один круг цикла. То есть медленный прошел путь x + y, а большой x + y + z + y. Учитывая, что быстрый указатель вдвое быстрее медленного, получим равенство:

2 (x + y) = x + y + z + y или x = z

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

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

ListNode* detectCycle(ListNode *head)

{

if (!head) return NULL;

Устанавливаем указатели 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)

{

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

q = head;

Двигаем указатели p и q на одну позицию вперед пока они не встретятся.

while (p != q)

{

p = p->next;

q = q->next;

}

Указатели p и q встретятся в вершине, которая является началом цикла. Возвращаем указатель на эту вершину.

return p;

}

}

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

return NULL;

}

Java реализация

ListNode detectCycle(ListNode head)

{

if (head == null) return null;

ListNode p = head;

ListNode q = head;

while(q.next != null && q.next.next != null)

{

p = p.next;

q = q.next.next;

if (p == q)

{

q = head;

while (p != q)

{

p = p.next;

q = q.next;

}

return p;

}

}

return null;

}