链表 - 在索引处查找第 N 个元素

Question

我在链表的特定索引处查找元素的代码出现问题。

findElement(index) {
let currentNode = this.head;
let count = 0;
while (currentNode != null) {
if (count === index) {
return currentNode;
count++;
currentNode = currentNode.next;
}
return -1;
}
}

当我这样做时，我得到的是整个链表而不是一个特定的节点。因此，如果我控制台.log(list.findElement(0((，我会得到整个链表。但是如果我控制台日志控制台.log(list.findElement(1((，我会得到-1。但我想要的是第二个节点。下面是我的其余代码。不完全确定我的 findElement 函数出了什么问题。

class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}
class LinkedList {
constructor() {
this.head = null;
//Length
this.length = 0;
}
//Push-front
pushFront(value) {
let node = new Node(value);
node.next = this.head;
this.head = node;
this.length++;
}
//Pop-front
popFront() {
if (this.head != null) {
this.head = this.head.next;
}
this.length--;
}
//Push-back
pushBack(value) {
let node = new Node(value);
if (this.head === null) {
this.head = node;
} else {
let currentNode = this.head;
while (currentNode.next) {
currentNode = currentNode.next;
}
currentNode.next = node;
}
this.length++;
}

Answer 1

findElement函数中的逻辑存在一些问题。主要问题是count永远不会从 0 开始改变，因此该函数仅在头部是所寻求的元素时才有效(例如index === 0( 并在任何其他输入上返回-1(此"失败"返回应完全移出while循环(。

这是一个包含count++的版本，currentNode = currentNode.next移动到if之外的隐式else：

findElement(index) {
let currentNode = this.head;
let count = 0;
while (currentNode) {
if (count === index) {  // found the element
return currentNode;
}

count++;  // increment counter
currentNode = currentNode.next;  // move to next node
}

return -1;
}

另一个问题是，如果在空列表上调用，您的popFront会将列表的长度减少到-1。递减应该是有条件的，也是有条件的。这可能会在将来的实现中造成伤害，但由于您从不使用列表长度，因此您可以完全删除它。

综上所述，这是一个测试程序：

class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}
class LinkedList {
constructor() {
this.head = null;
this.length = 0;
}

findElement(index) {
let currentNode = this.head;
let count = 0;
while (currentNode) {
if (count === index) {
return currentNode;
}

count++;
currentNode = currentNode.next;
}

return -1;
}
pushFront(value) {
const node = new Node(value);
node.next = this.head;
this.head = node;
this.length++;
}
popFront() {
if (this.head != null) {
this.head = this.head.next;
this.length--;
}
}
pushBack(value) {
const node = new Node(value);
if (this.head === null) {
this.head = node;
} 
else {
let currentNode = this.head;
while (currentNode.next) {
currentNode = currentNode.next;
}

currentNode.next = node;
}

this.length++;
}
}

const ll = new LinkedList();
ll.pushBack(1);
ll.pushBack(2);
ll.pushBack(3);
console.log(ll);
console.log(`First node: ${ll.findElement(0).value}`);
console.log(`Second node: ${ll.findElement(1).value}`);
console.log(`Third node: ${ll.findElement(2).value}`);
console.log(`Invalid index: ${ll.findElement(22).value}`);

Answer 2

你有一个return语句作为if (count === index)条件的第一行，这可以防止进一步的代码执行(意味着currentNode = currentNode.next永远不会到达(。

您希望将return currentNode向下移动两行，以便在函数返回之前引用后续节点。

findElement(index) {
let currentNode = this.head;
let count = 0;
while (currentNode != null) {
if (count === index) {
count++;
currentNode = currentNode.next;
return currentNode;
}
return -1;
}
}