在 JavaScript 中反转链表的策略 [英] strategies to reverse a linked list in JavaScript
问题描述
我刚刚解决了一个简单的面试问题:请反转单向链表.
I just struggled through a simple interview question: Please reverse a singly linked list.
虽然我没能及时提供有效的答案来挽救面试,但我事后想出了一个解决方案.
While I failed to provide a working answer in time to save the interview, I was able to come up with a solution afterwards.
我的解决方案是否正确?你会如何用 Big-Oh 来分析这个?有没有更有效的方法来反转单链表?
Is my solution correct? How would you analyze this with Big-Oh? Are there more efficient ways to reverse a singly linked list?
// reverse a linked list
var reverseLinkedList = function(linkedlist) {
var node = linkedlist;
var previous = null;
while(node) {
// reverse pointer
node.next = previous;
// increment previous to current node
previous = node;
// increment node to next node
if (node.next){
node = node.next
} else {
node = null;
}
}
}
注意:在我搜索类似帖子时,我确实在 JavaScript 中找到了一个示例.我想知道我的代码是否可行(没有 temp
变量).谢谢.
Note: In my search for similar posts, I did find one example in JavaScript. I was wondering if my code is possible (without a temp
variable). Thank you.
推荐答案
您的代码存在一些问题.这应该说清楚.
There are a couple of problems with your code. This should make it clear.
// reverse a linked list
var reverseLinkedList = function(linkedlist) {
var node = linkedlist;
var previous = null;
while(node) {
// save next or you lose it!!!
var save = node.next;
// reverse pointer
node.next = previous;
// increment previous to current node
previous = node;
// increment node to next node or null at end of list
node = save;
}
return previous; // Change the list head !!!
}
linkedlist = reverseLinkedList(linkedlist);
这篇关于在 JavaScript 中反转链表的策略的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!