在 JavaScript 中反转链表的策略
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/23278017/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
strategies to reverse a linked list in JavaScript
提问by user2954463
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.
虽然我未能及时提供有效的答案来保存采访，但我后来能够想出一个解决方案。
Is my solution correct? How would you analyze this with Big-Oh? Are there more efficient ways to reverse a singly linked list?
我的解决方案是否正确？你会如何用 Big-Oh 来分析这个？是否有更有效的方法来反转单链表？
// 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;
}
}
}
Note: In my search for similar posts, I did find one examplein JavaScript. I was wondering if my code is possible (without a tempvariable). Thank you.
注意：在我搜索类似帖子时，我确实在 JavaScript 中找到了一个示例。我想知道我的代码是否可行（没有temp变量）。谢谢你。
回答by stark
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);
回答by Rantelo
You could solve this problem recursively in O(n) time as ckerschmentions. The thing is, that you need to know that recursion is memory intensive since functions accumulate in the calls stack until they hit the stop condition and start returning actual things.
正如ckersch提到的，您可以在 O(n) 时间内递归地解决这个问题。问题是，您需要知道递归是内存密集型的，因为函数会在调用堆栈中累积，直到它们达到停止条件并开始返回实际事物。
The way I'd solve this problem is:
我解决这个问题的方法是：
const reverse = (head) => {
if (!head || !head.next) {
return head;
}
let temp = reverse(head.next);
head.next.next = head;
head.next = undefined;
return temp;
}
When reverse() reaches the end of the list, it will grab the last node as the new head and reference each node backwards.
当 reverse() 到达链表末尾时，它会抓取最后一个节点作为新的头部，并反向引用每个节点。
回答by ckersch
This would be O(n) in time, since you do a constant number of operations on each node. Conceptually, there isn't a more efficient way of doing things (in terms of big-O notation, there's some code optimization that could be done.)
这将是 O(n) 时间，因为您在每个节点上执行恒定数量的操作。从概念上讲，没有更有效的做事方式（就大 O 表示法而言，可以进行一些代码优化。）
The reason why you can't exceed O(n) is because, in order to do so, you would need to skip some nodes. Since you need to modify each node, this wouldn't be possible.
你不能超过 O(n) 的原因是，为了做到这一点，你需要跳过一些节点。由于您需要修改每个节点，因此这是不可能的。
Efficiency then comes down to a constant factor. The fewer operations you can do per item in the list, the faster your code will execute.
然后效率归结为一个恒定因素。列表中每个项目可以执行的操作越少，代码执行的速度就越快。
I'd implement like this:
我会这样实现：
function reverseLinkedList(list, previous){
//We need to use the the current setting of
//list.next before we change it. We could save it in a temp variable,
//or, we could call reverseLinkedList recursively
if(list.next !== null){
reverseLinkedList(list.next, list);
}
//Everything after 'list' is now reversed, so we don't need list.next anymore.
//We passed previous in as an argument, so we can go ahead and set next to that.
list.next = previous;
}
reverseLinkedList(list, null);
Of course, this is recursive, so it would be inefficient in terms of space, but I like recursive code :)
当然，这是递归的，所以在空间方面效率很低，但我喜欢递归代码:)
This also doesn't return the reversed linked list, but we could fairly easily modify things to do so if that were important.
这也不会返回反向链接列表，但如果这很重要，我们可以很容易地修改它。
回答by ASHISH RANJAN
//O(n) | O(1) wherre n is the number of nodes in the linked list
class Node{
constructor(val){
this.val = val;
this.next = null;
}
}
function reverseLinkedList(head) {
if(!head) return null;
let p1 = head;
let p2 = null;
while(p1){
let temp = p1.next;
p1.next = p2;
p2 = p1;
p1 = temp;
}
return p2;
}
const a = new Node(1);
a.next = new Node(2);
a.next.next = new Node(3)
console.log("Current Node",a);
console.log("Reversed List",reverseLinkedList(a))回答by Abhijeet
ES6 solution: Just keep a track of the reversed list and keep adding that to tmp.
ES6 解决方案：只需跟踪反向列表并将其添加到 tmp。
const reverseLinkedList = (head) => {
let reversed = null;
while(head) {
const tmp = head;
head = head.next;
tmp.next = reversed;
reversed = tmp;
}
return reversed;
};
console.log(JSON.stringify(reverseLinkedList({
data: 1,
next: {
data: 2,
next: {
data: 3,
next: {
data: 4,
next: {
data: 5,
next: {
data: 5,
next: {
data: 6
}
}
}
}
}
}
})));
