反向链接列表 - Javascript - 使用类或只定义一个函数？以及如何计算时间/空间复杂度

Question

我知道有一些使用javascript的反向链接列表问题，但我希望更清楚地了解其他人提供的解决方案。

是否需要使用class LinkedList来声明一个链表，或者只是按照这个例子给出工作？

我只是不清楚这个函数是如何声明一个名为reverseLinkedList的变量并解决它而不是实际使用该类。

不确定这是否有意义，但除此之外，这个解决方案是否足够明确以解决扭转链表问题？

此外，这会被视为时间复杂度的O（n）吗？因为它有一个while循环，设置有限的时间运行。而且我不确定空间复杂性。

// reverse a linked list
const reverseLinkedList = (linkedlist) => {
  let node = linkedlist;
  let previous = null;

  while(node) {
// save next or you lose it!!!
  let 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);

Answer 1

这里有几件事情要发生

首先是这个宣言

let reverseLinkedList = function(linkedlist) {

类似于这个声明

function reverseLinkedList(linkedList) {

除了你不能调用reverseLinkList，直到它在第一个例子中被声明。您可以在这里阅读更多关于吊装的信息

var functionName = function() {} vs function functionName() {}

第二次使用类或函数并不重要。你会看到Javascript中的类实际上只是语法糖（但是你可以在这里阅读一些问题）

are es6 classes just syntactic sugar for the prototypal pattern in javascript?

最后，这个函数的时间复杂度是O（n），因为它只是遍历列表一次。

希望有所帮助！

Answer 2

无论哪种方式都没关系。创建一个类LinkedList将允许您添加方法，但它解决单个反向链表问题是过度的。

链表只是节点的集合，其中每个节点使用next对象属性引用下一个节点。

如果你想在LinkedList中添加一堆便利方法，那么是的，一个类会很有用。但是对于像列表反转这样的单个问题，您发布的解决方案假定该函数将列表中的第一个节点作为输入，并且每个节点（只是一个JavaScript对象）具有next属性。

例如，假设我正在解决多个链表问题，我还需要从一组值中创建一个链表。假设我还想轻松测试函数（例如reverseLinkedList）是否返回正确的列表。我可以使用像this这样的课程

然后，测试上面的解决方案就像下面这样简单：

首先，重写反向解决方案，使其获取一个链接列而不仅仅是头部，因此您可以在反转后修改列表的head属性：

const reverseLinkedList = (linkedlist) => {
  let node = linkedlist.head;
  let previous = null;

  while(node) {
// save next or you lose it!!!
  let 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;
}
  linkedlist.head = previous
  return previous;   // Change the list head !!!
}

然后你可以运行这个测试：

var inputList = new LinkedList([1,2,3,4])
var expectedReversedList = new LinkedList([4,3,2,1])
var actualReversedList = reverseLinkedList(inputList)
console.log(inputList.isEqualTo(actualReversedList))

此外，在空间和时间复杂性方面，由于上述解决方案使对象发生变异，因此它是O（1）空间，并且由于它只通过节点迭代一次，因此它的O（N）时间复杂度