javascript - 如何在javascript中递归地反转链表？

Question

我正在尝试在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);

有人可以帮助我吗？

Answer 1

假设您的列表与此类似:

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 ]