Прежде всего, что касается колец в таблице с одной цепочкой, как правило, возникают следующие проблемы:
1. Приведите таблицу с одной цепочкой, чтобы определить, есть ли в ней кольца;
2. Если есть кольцо, выясните точку входа кольца;
3. Если есть кольцо, найдите количество узлов на кольце;
4. Если есть ссылка, найдите длину списка;
5. Если есть кольцо, найдите самую дальнюю точку (противоположный узел) на кольце от любого узла;
6. (расширение) как определить, пересекаются ли два ациклических списка;
7. (расширение) если пересекается, найдите первый пересекающийся узел;
Далее я дам пояснения и соответствующие коды для вышеупомянутых семи вопросов один за другим.
1. При оценке есть кольцо (указатель заголовка цепочки-голова)
Для решения этой проблемы мы можем использовать метод “быстрый и медленный указатель”. Есть два указателя, быстрый и медленный. В начале оба указателя указывают на начало заголовка цепочки, а затем на каждом шаге
В операции медленное движение вперед на один шаг, то есть – > далее, в то время как быстрое движение вперед на два шага, то есть – > далее – > далее.
Поскольку быстрое движется быстрее, чем медленное, если есть кольцо, быстрое войдет в кольцо первым, а медленное войдет в кольцо позже. Когда обе руки входят в кольцо, после определенного этапа операции
Они должны быть в состоянии встретиться друг с другом на ринге, и в это время медленный не сделал круг, то есть они должны встретиться до того, как медленный закончит первый круг. Доказательство можно увидеть на следующем рисунке:
Когда slow просто входит в кольцо, каждый указатель может находиться в описанной выше ситуации. Затем медленно и быстро двигайтесь вперед соответственно, то есть:
if (slow != NULL && fast->next != NULL)
{
slow = slow -> next ;
fast = fast -> next -> next ;
} Другими словами, когда медленный движется вперед по одному шагу за раз, быстрый делает два шага вперед, поэтому после каждого шага расстояние между быстрым и медленным сокращается на один шаг, так что, если это будет продолжаться, расстояние между ними постепенно сокращается: 5, 4, 3, 2, 1, 0 – > встречаемся. И поскольку расстояние между быстрым и медленным в одном и том же кольце не превышает длину коммутации, поэтому
К моменту их встречи медленный, должно быть, не заканчивал ходить в течение недели (или сразу после ходьбы, это происходит в начале, когда быстрый и медленный находятся у входа в кольцо).
Вопрос 1: есть ли кольцо?
typedef struct node{
char data ;
node * next ;
}Node;
bool exitLoop(Node *head)
{
Node *fast, *slow ;
slow = fast = head ;
while (slow != NULL && fast -> next != NULL)
{
slow = slow -> next ;
fast = fast -> next -> next ;
if (slow == fast)
return true ;
}
return false ;
}Точка входа в кольцо вопроса 2: Из приведенного выше анализа известно, что, когда быстрые и медленные встречаются, медленный не закончил список цепей, предполагая, что быстрый прошел n (1) циклов в кольце. Если медленный делает шаг s, быстрый делает шаг 2S И из-за Количества шагов, которое имеет быстрый + n * r (s + N циклов, которые были добавлены в кольцо), то существует следующее уравнение: 2 s + n r;(1) =>*r;(2)
Если предполагается, что длина всего связанного списка равна l, расстояние между входом и точкой встречи равно x (как показано на рисунке выше), а расстояние между начальной точкой и точкой входа равно a (как показано на рисунке выше), то есть: A + * r; (3) из (2) a + x = (n – 1) r + r = (n – 1) R + (L – a) (4) из длины общей длины списка – расстояние от начальной точки до точки входа a = (n – 1) * r + (L-a-x) (5) Из уравнения (5) и рисунка выше мы видим, что расстояние a от начальной точки в начале списка до точки входа такое же, как расстояние a от точки встречи (как показано на рисунке) медленно и быстро до точки входа. Таким образом, мы можем использовать указатель (PTR1, Prt2) соответственно. В то же время мы можем начать с точки встречи головы, медленно и быстро, и идти по одному шагу за раз до PTR1. В это время позиция является точкой входа! Вторая проблема также заключалась в
Node* findLoopStart(Node *head)
{
Node *fast, *slow ;
slow = fast = head ;
while (slow != NULL && fast -> next != NULL)
{
slow = slow -> next ;
fast = fast -> next -> next ;
if (slow == fast) break ;
}
If (slow = = null | fast - > next = = null) return null; // no ring, return null
Node * PTR1 = head; // starting point of list
Node * ptr2 = slow; // meeting point
while (ptr1 != ptr2)
{
ptr1 = ptr1 -> next ;
ptr2 = ptr2 -> next ;
}
Return PTR1; // find the entry pointВ-третьих, если есть кольцо, найдите количество узлов на кольце:
Способ 1: запишите временную переменную tempptr, хранящуюся в узле встречи, а затем позвольте медленному (или быстрому, все равно) продолжать двигаться вперед – > далее; до замедления; в это время количество пройденных шагов равно количеству узлов на кольце; Режим 2: с точки встречи медленно и быстро продолжайте двигаться вперед первоначальным способом – > далее; – > далее – > далее; пока два проекта снова, в это время количество шагов равно количеству узлов на кольце. Суть этих двух способов одна и та же. Они снова начинают ходить по месту встречи, пока снова не встретятся.
Задача 4 состоит в том, чтобы найти длину связанного списка, если есть кольцо: расстояние от начальной точки до точки входа было известно в вопросе 2, а длина кольца r была известна в вопросе 3. Длина цепи от начальной точки до точки входа + длина кольца R;
Задача 5 состоит в том, чтобы найти самую дальнюю точку (противоположный узел) на кольце от любого узла.
Как показано на рисунке ниже, точки 1 и 4, 2 и 5, 3 и 6 являются “противоположными узлами” друг друга, то есть для замены самой дальней точки нам необходимо выяснить, как заменить самую дальнюю точку любой точки. Чтобы заменить любую точку на 0, нам нужно найти ее “противоположную точку”. Мы можем думать так: используйте описанный выше метод быстрого и медленного указателя, позвольте медленному и быстрому указывать на ptr0 и выполняйте ту же операцию, что и выше, на каждом шаге (один шаг для медленного и два шага для быстрого). Когда или – > далее, узел, на который указывает замедление, является “противоположным узлом” ptr0. Как показано на рисунке выше, давайте представим, что кольцо может быть расширено от бензина до бесконечной длины (повторите предыдущее содержимое после 6 выше), как показано на рисунке выше. Теперь проблема проста. Поскольку расстояние медленного перемещения всегда является общим для fast, когда fast пересекает r узлов, играющих по всей длине кольца, slow просто пересекает R/2 узла. То есть в это время он указывает на точку, наиболее удаленную от ptr 0.
Перепечатка: https://blog.csdn.net/doufei…