反向链接列表的策略 [英] strategies to reverse a linked list in JavaScript

问题描述

我只是在一个简单的面试问题中苦苦挣扎:请扭转一个单链表.

I just struggled through a simple interview question: Please reverse a singly linked list.

虽然我未能及时提供有效的答案来保存面试，但后来我能够提出解决方案.

While I failed to provide a working answer in time to save the interview, I was able to come up with a solution afterwards.

我的解决方案正确吗?您将如何使用Big-Oh对此进行分析?是否有更有效的方法来反转单链列表?

Is my solution correct? How would you analyze this with Big-Oh? Are there more efficient ways to reverse a singly linked list?

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

注意:在搜索相似的帖子时，我确实在JavaScript中找到了一个示例.我想知道我的代码是否可行(没有temp变量).谢谢.

Note: In my search for similar posts, I did find one example in JavaScript. I was wondering if my code is possible (without a temp variable). Thank you.

推荐答案

您的代码有两个问题.这应该很清楚.

There are a couple of problems with your code. This should make it clear.

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

这篇关于反向链接列表的策略的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！