我正在解决LeetCode问题141. Linked List Cycle:
给定
head
(linked list的头部),确定该linked list中是否有一个循环.如果列表中有某个可以通过连续跟随
next
指针再次到达的 node ,则该列表中存在一个循环.在内部,pos
用于表示tail的next
指针所连接的 node 的索引.Note that 101 is not passed as a parameter.返回
true
if there is a cycle in the linked list.否则,返回false
.例1:
Input:
head = [3,2,0,-4], pos = 1
Output:true
Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).
我的原始解决方案(版本A)超出了上述输入的时间限制.我最终能够通过更改two lines of code(版本B)足够快地制定解决方案,解决方案被接受并且在某种程度上更高效.
为什么Version B比Version A快?为什么变量分配比使用原始对象更快/更有效?
我改变了这个.
版本 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;
};
对此.
版本 B ( 工作溶液 )
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;
};