javascript - 链表 - 在索引处查找第 N 个元素
问题描述
我的代码在链接列表的特定索引处查找元素时遇到问题。
findElement(index) {
let currentNode = this.head;
let count = 0;
while (currentNode != null) {
if (count === index) {
return currentNode;
count++;
currentNode = currentNode.next;
}
return -1;
}
}
当我这样做时,我得到的是整个链表而不是一个特定的节点。因此,如果我使用 console.log(list.findElement(0)),我会得到整个链表。但是如果我控制台日志console.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++;
}
解决方案
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) {
let 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) {
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++;
}
}
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}`);
推荐阅读
- office-ui-fabric - Office-ui-fabric-react 选择组在与文本字段相同的组件中时行为不正确
- excel - 我使用 INDEX 和 MATCH 与 excel 来返回我想要的值,但我可以让它在匹配中它必须匹配两组数据而不是一组?
- java - nio 包中等效的 java.io.InputStream#available() 方法
- python - 使用 Python 中的 BeautifulSoup 从新闻网站主页抓取标题
- r - csv.read 将每个逗号视为行分隔符
- python - 在类中使用 Selenium
- javascript - NodeJS parquet-reader - 如何从变量而不是文件中读取?
- drupal - Drush 9 sql:同步错误:找不到源@local的数据库记录
- php - pg_query():查询失败:SSL SYSCALL 错误:在 php 脚本中检测到 EOF
- c# - Dispatcher.CurrentDispatcher 导致 ReactiveUI 调用挂起