我试图在Javascript中递归地逆转linkedlist。我自己试过了，也在网上找过了。但没有成功。下面是我尝试的代码:
var Node = (function(){
function Node(val){
this.elem = val;
this.next = null;
}
return Node;
})();
var SLinkedlist = (function(){
function SLinkedlist(){
this.head = new Node("head");
}
return SLinkedlist;
})();
SLinkedlist.prototype.find = function(val){
var current = this.head;
while(current !== null && current.elem !== val){
current = current.next;
}
return current;
}
SLinkedlist.prototype.insert = function(newVal, val){
var current = this.find(val);
var newNode = new Node(newVal);
newNode.next = current.next;
current.next = newNode;
}
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
console.log(list);
if(list !== null && list.next !==null){
reverseLinkedList(list.next, list);
}
console.log("after recursion!")
console.log(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.head, null);
有人能帮我吗?
假设您的列表与此类似:
var list =
{
name: "1",
next: {
name: "2",
next: {
name: "3",
next: {
name: "4"
}
}
}
};
console.log("Original list");
var head = list;
while (head != undefined) {
console.log(head.name);
head = head.next;
}
呈现
Original list
1
2
3
4
你可以用递归函数反转它，像这样:
head = reverse(list, undefined);
console.log("Reverse list");
while (head != undefined) {
console.log(head.name);
head = head.next;
}
function reverse(list, prev) {
// if this is the last node, switch it with previous and return
if (list.next == undefined) {
list.next = prev;
return list;
}
// otherwise, switch it with the reverse of what is next
var ret = reverse(list.next, list);
list.next = prev;
return ret;
}
呈现
Reverse list
4
3
2
1
它是如何工作的?它基于以下原则:
Reverse([1 2 3 4]) ==
[ Reverse([2 3 4]) 1 ] ==
[ Reverse([3 4]) 2 1 ] ==
[ 4 3 2 1 ]
这是我的面向对象递归解决方案。
function Node(value) {
this.value = value;
this.next = null;
}
function SLinkedList(node) {
if (node) {
this.head = node;
} else {
this.head = null;
}
}
SLinkedList.prototype.prepend = function(node) {
node.next = this.head;
this.head = node;
}
SLinkedList.prototype.print = function() {
var arr = [];
var current = this.head;
while (current !== null) {
arr.push(current.value);
current = current.next;
}
alert(arr.join(' '));
}
SLinkedList.prototype.reverse = function() {
if (this.head === null || this.head.next === null) {
return;
}
var first = this.head;
var rest = new SLinkedList(this.head.next);
rest.reverse();
first.next.next = first;
first.next = null;
this.head = rest.head;
}
var list = new SLinkedList();
list.prepend(new Node(4));
list.prepend(new Node(3));
list.prepend(new Node(2));
list.prepend(new Node(1));
list.print();
list.reverse();
list.print();
JSFiddle: http://jsfiddle.net/5c9gtstk/1/
关于你的代码的一些提示，不是100%错误，但我认为会有所帮助，主要是为了复习你的链表:
- 这是不典型的有一个"头"作为值的第一个节点，虽然你可以做到这一点-只是从你的"头"节点的
next开始。 -
console.log(list)行没有告诉太多关于发生了什么，因为数据结构只包含elem和next，这就是为什么我写了一个打印函数。这可以帮助你调试。 - 你的插入函数也是非典型的，但这不是一个真正的问题在这个算法:)
http://www.thatjsdude.com/interview/linkedList.html#singlyLinkedList有一个简单、简明的解释，告诉你如何做到这一点。
关于你的反向算法，你几乎有了正确的想法。我在这里给出的主要技巧是绘制出递归调用中发生的事情!慢慢地手动一步一步地执行代码。这需要几秒钟的时间，但会让一切都100%清楚。
具体来说，在反转列表的其余部分后，list.next = previous;是所有您需要做的吗?还有一些其他的指针需要修改。
其他人，包括这里的一个答案，已经给出了比我更好的解释。同样，图表是关键。http://www.geeksforgeeks.org/write-a-function-to-reverse-the-nodes-of-a-linked-list/有一个很好的、简短的解释——直接跳到递归方法的部分。
我上面的2个链接是1个浏览器页面。我建议你看一看
要反转链表，我们可以使用简单的递归方法。将链表的头传递给下面的方法。
reverse( head ) {
if( head ) {
reverse( head.next );
console.log( head.data );
}
}
完整的工作解决方案在这里
为了补充上述答案，下面是ES6/JavaScript中的后进先出(LIFO)链表实现，具有递归地反转列表和就地(不创建新列表)的函数:
class Element {
constructor(value) {
this.value = value;
this.next = null;
}
}
class List {
constructor(arr) {
this.head = null;
if (arr) {
arr.forEach(el => this.add(new Element(el)));
}
}
get length() {
return this.head ? this.countElements(1, this.head) : 0;
}
add(el) {
const element = el;
element.next = this.head;
this.head = element;
}
countElements(count, element) {
return element.next ? this.countElements(count + 1, element.next) : count;
}
toArray(arr = [], element = this.head) {
arr.push(element.value);
return element && element.next ? this.toArray(arr, element.next) : arr;
}
reverse(prev = null) {
if (this.head.next) {
const current = this.head;
this.head = this.head.next;
current.next = prev;
return this.reverse(current);
}
this.head.next = prev;
return this;
}
}
const list = new List([1, 2, 3, 4, 5, 6, 7 , 8 ,9 , 10]);
console.log(list.toArray().toString()); // returns LIFO list as array (last list el = first array el)
console.log(list.reverse().toArray().toString()); // returns LIFO list reversed as array(first first)这两个现有的答案为这个问题提供了很好的解决方案，但是我认为了解代码为什么不能工作可能会有所帮助。在javascript中，当执行递归调用时，将创建一个具有自己作用域的新闭包。所以在最后一个调用中，也就是"tail"所在的地方，引用它的list变量实际上是一个局部变量，它覆盖了环境中现有的list。因此，当函数退出时，如果不返回这个本地list，对它的引用将丢失。
其他两个答案所做的是返回该值并将其存储在临时变量中(代码中的注释实际上没有帮助…你需要把尾巴存储在某个地方，否则你会丢失它!)
您可能知道，如果所有这些都在您的反向函数中处理，则不会污染全局作用域。
另外@bbill是绝对正确的手动执行代码，一步一步地在像Chrome devtools这样的东西。这真的可以很好地了解正在发生的事情。
你可以试试这个方法:我从这里参考:https://www.youtube.com/watch?v=KYH83T4q6Vs基本上，一旦递归到达最后一个节点，我们就会将指针从最后一个节点更改为指向前一个节点。
class LinkedList {
constructor() {
this.head = null;
this.size = 0;
}
reverseLLRec(node) {
if (!node.next) {
this.head = node;
return;
}
this.reverseLLRec(node.next);
const curr = node.next;
curr.next = node;
node.next = null;
}
}
class Node {
constructor(val) {
this.val = val;
this.next = null;
}
}
class LinkedList {
constructor() {
this.head = null;
this.size = 0;
}
reverseLLRec(node) {
if (!node.next) {
this.head = node;
return;
}
this.reverseLLRec(node.next);
const curr = node.next;
curr.next = node;
node.next = null;
}
insertAtLast(data) {
const node = new Node(data);
if (this.head === null) {
this.head = node;
} else {
let current = this.head;
while (current.next) {
current = current.next;
}
current.next = node;
}
}
printList() {
let curr = this.head;
let list = [];
while (curr) {
list.push(curr.val);
curr = curr.next;
}
console.log(list);
}
}
const ll = new LinkedList();
ll.insertAtLast(1);
ll.insertAtLast(2);
ll.insertAtLast(3);
ll.insertAtLast(4);
ll.insertAtLast(5);
console.log('Before reverse:');
ll.printList();
ll.reverseLLRec(ll.head);
console.log('After reverse:');
ll.printList();