142. Linked List Cycle II
Given a linked list, return
the node where the cycle begins. If there is no cycle, return null.
Do not modify the linked
list.
Can you solve it without
using extra space?
142. Цикл в связном списке II
Задан связный список. Верните
указатель на вершину, в которой начинается цикл. Если цикла нет, верните null.
Не модифицируйте связный
список.
Решите задачу с константной
памятью.
// C++
/**
*
Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode
*detectCycle(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 ListNode detectCycle (ListNode head) {
}
}
РЕШЕНИЕ
список
Анализ алгоритма
При помощи двух указателей
(медленного и быстрого) определим, содержит ли связный список цикл. Пусть
список содержит цикл, а p указывает
на вершину, в которой быстрый указатель догнал медленный. Установим q на начало списка.
Пусть расстояние от начала
до вершины, в которой начинается цикл, равно x. Расстояние от начала цикла до точки встречи двух указателей
равно y. Расстояние от вершины, на
которую указывает p, до начала цикла
по ходу списка равно z.
Предположим, что указатели
встретились так, что быстрый прошел только один круг цикла. То есть медленный
прошел путь x + y, а большой x + y + z
+ y. Учитывая, что быстрый указатель
вдвое быстрее медленного, получим равенство:
2 (x + y) = x + y
+ z + y или x = z
Это означает, что теперь
достаточно итеративно двигать указатели p
и q на один шаг пока они не
сравняются. Причем это обязательно случится в вершине, которая является началом
цикла.
Реализация алгоритма
class Solution
{
public:
ListNode *detectCycle(ListNode
*head)
{
if (!head) return
NULL;
ListNode* p = head;
ListNode* q = head;
while(q->next && q->next->next)
{
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;
}
};
Java реализация
class Solution
{
public 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;
}
}