使用递归的反向链表问题

Question

我正在尝试使用递归来反转链表。一切都很顺利，直到最后，我得到了一个破碎的结果。

有人能告诉我我做错了什么吗？

const reverseLinkedList = (node, newChildOldParent=null ) => {
if( node.next ){
reverseLinkedList(node.next, node);
}
node.next = newChildOldParent;
return node;
}
const someList = {
value: 1,
next: {
value: 2,
next: {
value: 3,
next: {
value: 4,
next: null
}
}
}
};
console.log(reverseLinkedList( someList ))

我得到

{ value: 1, next: null }

而不是反向链表。

我哪里错了？

Answer 1

反转工作正常，但您已经失去了对新磁头的跟踪，而是返回了现在指向null的旧磁头。下面是堆栈调用的图表：

curr: 1 next: 2
curr: 2 next: 3
curr 3: next: 4
curr: 4 next: null
curr: 4 next: 3
curr: 3 next: 2
curr: 2 next: 1
curr: 1 next: null <-- uh oh

您需要跟踪新的头，即节点4。下面是另一种将最后一个节点传递回头部的方法：

const reverseLinkedList = (curr, prev) => {
if (curr.next) {
const newHead = reverseLinkedList(curr.next, curr);
curr.next = prev;
return newHead; // pass the new head up the list
}

curr.next = prev;
return curr; // base case; return the tail
};
const someList = {
value: 1,
next: {
value: 2,
next: {
value: 3,
next: {
value: 4,
next: null
}
}
}
};
console.log(reverseLinkedList(someList));