javascript - 在 JavaScript 中反转链表的策略

Question

我只是在一个简单的面试问题上苦苦挣扎:请反转单向链表。

虽然我未能及时提供工作答案以挽救采访，但我后来想出了一个解决方案。

我的解决方案是否正确？你会如何用 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;
    }
  }
}

注意:在我搜索类似帖子时，我确实找到了 one example在 JavaScript 中。我想知道我的代码是否可行(没有 temp 变量)。谢谢。

Answer 1

您的代码存在一些问题。这应该说清楚了。

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