Решение циклических проблем связанных списков с использованиемverseList
Недавно я попытался решить проблему с LeetCode 141, Цикл связанных списков:
Учитывая
head, заголовок связанного списка, определите, есть ли в связанном списке цикл.В связанном списке существует цикл, если в списке есть какой-то узел, к которому можно снова добраться, непрерывно следуя по указателю
next. [...]Верните
true, если в связанном списке есть цикл. В противном случае вернитеfalse.
Я нашел решение, которое меняет связанный список. Это казалось многообещающей идеей.
Вопрос
Я был бы признателен за некоторые разъяснения о том, как работает это конкретное решение. Я озадачена тем, как head->next может быть NULL, если нет цикла. Разве он не должен указывать на второй узел после реверса?
Вот код:
/**
* 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)
{
if (head){
reverseList(head);
if (head->next != NULL)
{
return true;
}
}
return false;
}
void reverseList(ListNode *head)
{
ListNode *temp = head;
ListNode *next = head->next;
head->next = NULL;
while (temp != NULL)
{
temp = next;
if (next != NULL)
{
next = temp->next;
temp->next = head;
head = temp;
}
}
}
};
Ответы 1
Подход с разворотом — это изящный трюк, позволяющий определить, существует ли цикл или нет. Есть два случая для анализа:
Список ввода не имеет цикла
Об этом сценарии вы написали:
Я озадачена тем, как
head->nextможет бытьNULL, если нет цикла.
В reverseList это делается явно с помощью присваивания: head->next = NULL и поскольку этот узел больше не посещается во время алгоритма реверса, это окончательно.
Разве он не должен указывать на второй узел после реверса?
Возможно, путаница возникает из-за предположения, что после переворота переменная head будет ссылаться на первый узел перевернутого списка, но это не так. Переменная head в hasCycle никогда не обновляется, поэтому она продолжает ссылаться на тот же узел, который был первым узлом списка, но стал хвостом после завершения обращения.
Например, если входной список:
head
↓
1 → 2 → 3 → 4 → null
... тогда разворот сделает это:
head
↓
null ← 1 ← 2 ← 3 ← 4
Ссылка на узел 4 возвращается основным вызовом reverseList, поскольку это новый заголовок теперь перевернутого списка. Но эта возвращенная ссылка игнорируется, поскольку она не нужна для этого алгоритма. Вместо этого мы сохраняем с помощью head ссылку на узел, который был головным до того, как произошел какой-либо разворот.
Список ввода имеет цикл
Это тот сценарий, о котором вы не спрашивали, но, на мой взгляд, его более интересно описать.
Возьмем в качестве примера этот список:
head
↓
1 → 2 → 3 → 4
↑ │
└───────┘
Теперь разворот будет происходить как обычно, и в какой-то момент этот процесс достигнет обратной ссылки:
head head' temp
↓ ↓ ↓
null ← 1 ← 2 ← 3 4
↑ │
└───────┘
↑
next
Это состояние непосредственно перед выполнением temp->next = head. (Я добавил апостроф для head', чтобы указать, что это локальная переменная в reverseList, а head по-прежнему остается переменной в hasCycle)
Итак, теперь часть списка, которая уже была перевернута, посещается снова, в противоположном направлении:
head head'
↓ ↓
null ← 1 ← 2 ← 3 ← 4
↑ ↑
next temp
И еще один шаг:
head
↓
null ← 1 2 ← 3 ← 4
│ ↑
└───────┘
↑ ↑ ↑
next temp head'
... и последний шаг:
head
↓
null 1 → 2 ← 3 ← 4
│ ↑
└───────┘
↑ ↑
temp head'
И здесь мы видим, что head->next снова указывает на второй узел в исходном порядке. Это эффект, который hasCycle можно обнаружить. В общем, вызов reverseList в списке, который имеет цикл, приведет к обращению цикла, но для узлов, которые не участвуют в этом цикле, будут восстановлены исходные ссылки. В полученном списке не будет узла со ссылкой next, то есть NULL.
Я надеюсь, что это проясняет ситуацию.
@ k314159, ты запускал этот код для такого связанного списка? Он работает нормально. Как я написал в конце своего ответа: «В общем, вызов reverseList в списке, имеющем цикл, приведет к обращению цикла, но для узлов, которые не участвуют в этом цикле, будут восстановлены исходные ссылки. " -- это общий эффект, независимо от того, где находится узел, на который имеется обратная ссылка.
Хорошее объяснение списка, в котором есть цикл назад к началу или всего 1 после начала. Но решение ОП не похоже на то, что оно будет работать для списка, в котором, например, 9-й элемент указывает на 5-й элемент. Это будет повторяться вечно, не так ли?