如何在javascript中递归地反转一个链表

假设您的列表与此类似:

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();