Я работаю над решением проблемы LeetCode 141. Цикл связанных списков:
Учитывая
head
, заголовок связанного списка, определите, есть ли в связанном списке цикл.В связанном списке существует цикл, если в списке есть какой-то узел, к которому можно снова добраться, непрерывно следуя по указателю
next
. Внутриpos
используется для обозначения индекса узла, к которому подключен указательnext
хвоста. Обратите внимание, чтоpos
не передается как параметр.Верните
true
, если в связанном списке есть цикл. В противном случае вернитеfalse
.Пример 1:
Ввод:
head = [3,2,0,-4], pos = 1
Вывод:true
Пояснение: В связанном списке есть цикл, хвост которого соединяется с узлом 1st (с индексом 0).
Мое исходное решение (версия A) превысило лимит времени, указанный выше. В конце концов мне удалось сделать решение достаточно быстрым, изменив две строки кода (Версия B), и решение было принято и в некотором смысле более эффективно.
Почему версия B быстрее, чем версия A? Почему назначение переменной происходит быстрее/эффективнее, чем использование исходного объекта?
Я изменил это...
/**
* @param {ListNode} head
* @return {boolean}
*/
var hasCycle = function(head) {
// create a fast pointer
let fastPointer = null;
// create a while loop that lasts for as long as head exists
while (head) {
// move fast pointer over by 2
fastPointer = head?.next?.next || null;
// if fastpointer is null, this indicates that there is no cycle so return false
if (fastPointer === null) return false;
// compare fastPointer to the slow pointer, if they are ever equal to the same node then the list contains a cycle.
if (fastPointer === head) return true;
// move head by 1
head = head.next;
}
// if the while loop ends, it indicates the there is no cycle so return false
return false;
};
к этому ...
var hasCycle = function(head) {
// create a fast pointer
let fastPointer = head; // !!!CHANGE #1
// create a while loop that lasts for as long as head exists
while (head) {
// move fast pointer over by 2
// !!!CHANGE #2 and solution worked!!!!
fastPointer = fastPointer?.next?.next || null;
// if fastpointer is null, this indicates that there is no cycle so return false
if (fastPointer === null) return false;
// compare fastPointer to the slow pointer, if they are ever equal to the same node then the list contains a cycle.
if (fastPointer === head) return true;
// move head by 1
head = head.next;
}
// if the while loop ends, it indicates the there is no cycle so return false
return false;
};
в первом решении, которое вы определяете
let fastPointer = null;
и затем вы делаете это:
fastPointer = fastPointer?.next?.next || null;
это означает, что вы пытаетесь переназначить переменную, а переменная уже равна нулю, это означает
fastPointer = null?.next?.next || null;
в первой опциональной цепочке оно уже равно нулю это означает следующее условие:
if (fastPointer === null)
истинно и вернет false, даже если у меня есть цикл и код не завершит выполнение
так что, по сути, это время не превышает "это сразу возвращает false...
Спрашивающий говорит, что они получают ошибку ограничения по времени. Почему вы настаиваете, что они этого не делают? Зачем им лгать об этом?
@trincot Я сам запускаю код в leetcode, и у меня не было превышения времени
Я предполагаю, что вы не запускали код спрашивающего, в котором возникла проблема, или что вы не запускали проблемный тестовый пример, например, случай «пример 1» (который упоминает спрашивающий). Наверняка код спрашивающего попадает в бесконечный цикл и, следовательно, достигает тайм-аута.
В ошибочной версии петля fastPointer
опережает на два узла по сравнению с head
. Но это означает, что fastPointer
на самом деле не движется быстрее... он находится всего на два узла впереди, но движется с той же «скоростью», что и head
. Что вам действительно нужно, так это то, чтобы fastPointer
увеличивал свое преимущество на каждом шаге, чтобы fastPointer
находился в связанном списке вдвое дальше, чем head
, а не всего на 2 узла впереди.
Это также объясняет, почему первая версия достигает ограничения по времени: она попадает в бесконечный цикл, когда во входном списке есть цикл, и этот цикл имеет размер, отличный от 2. В этом случае fastPointer
никогда не станет равным head
, поскольку находится ровно в 2 узлах от head
. Например, если в цикле 3 узла, то fastPointer
будет на 2 узла впереди head
и в конечном итоге (после прибытия в цикл) также на один узел позади head
. Это никогда не изменится: это расстояние останется прежним, поэтому цикл никогда не закончится.
На самом деле сейчас не самое подходящее время, чтобы спрашивать, поскольку вы можете тривиально добавить некоторую регистрацию в свои функции и профилировать, сколько ваших функций и циклов внутри ваших функций вызываются (и с какими значениями), чтобы вы могли выяснить, почему один набор инструкций занимает вечность, тогда как другой набор инструкций более эффективен. Сначала вам придется провести некоторую отладку самостоятельно.