用 JavaScript 实现链表操作 - 02 Length & Count

Batkid 发布于2019-08-22 10:47 / 1000人阅读

摘要：计算链表的长度和指定元素的重复次数。需求实现一个函数来计算链表的长度。递归版本递归是最有表达力的版本。注意因为要在外部作为返回值使用，我们只能用而不是声明变量。参考资料的代码实现的测试

TL;DR

计算链表的长度和指定元素的重复次数。系列目录见前言和目录。

需求

实现一个 length() 函数来计算链表的长度。

length(null) === 0
length(1 -> 2 -> 3 -> null) === 3

实现一个 count() 函数来计算指定数字在链表中的重复次数。

count(null, 1) === 0
count(1 -> 2 -> 3 -> null, 1) === 1
count(1 -> 1 -> 1 -> 2 -> 2 -> 2 -> 2 -> 3 -> 3 -> null, 2) === 4

length 递归版本

递归是最有表达力的版本。思路非常简单。每个链表的长度 length(head) 都等于 1 + length(head.next) 。空链表长度为 0 。

function length(head) {
  return head ? 1 + length(head.next) : 0
}

循环版本 - while

链表循环第一反应是用 while (node) { node = node.next } 来做，循环外维护一个变量，每次自增 1 即可。

function lengthV2(head) {
  let len = 0
  let node = head

  while (node) {
    len++
    node = node.next
  }

  return len
}

循环版本 - for

for 和 while 在任何情况下都是可以互换的。我们可以用 for 循环把变量初始化，节点后移的操作都放到一起，简化一下代码量。注意因为 len 要在 for 外部作为返回值使用，我们只能用 var 而不是 let/const 声明变量。

function lengthV3(head) {
  for (var len = 0, node = head; node; node = node.next) len++
  return len
}

count 递归版本

跟 length 思路类似，区别只是递归时判断一下节点数据。

function count(head, data) {
  if (!head) return 0
  return (head.data === data ? 1 : 0) + count(head.next, data)
}

循环版本

这里我直接演示的 for 版本，思路类似就不多说了。

function countV2(head, data) {
  for (var n = 0, node = head; node; node = node.next) {
    if (node.data === data) n++
  }
  return n
}

参考资料

Codewars Kata
GitHub 的代码实现
GitHub 的测试

GPU云服务器云服务器用javascript操作xml 多链表c语言实现 java实现链表插入遍历c语言实现链表

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/91243.html

用 JavaScript 实现链表操作 - 01 Push &amp; Build List

摘要：写两个帮助函数来创建链表。用于把一个节点插入到链表的头部。这个方法应该始终返回一个新的链表。接收一个数组为参数，创建对应的链表。参考资料的代码实现的测试 TL;DR 写两个帮助函数来创建链表。系列目录见前言和目录。需求写两个方法 push 和 buildList 来初始化链表。尝试在 buildList 中使用 push 。下面的例子中我用 a -> b -> c 来表示链表，...

Scorpion 2019-08-20 12:35 评论0 收藏0
用 JavaScript 实现链表操作 - 03 Get Nth Node

摘要：获得链表的第个节点。需求实现一个方法，传入一个链表和一个索引，返回索引代表的节点。递归版本假设函数定义为，递归过程为当为零，直接返回该节点，否则递归调用。如果循环结束还没有查到节点，那肯定是链表或者索引不合法，直接抛异常即可。 TL;DR 获得链表的第 N 个节点。系列目录见前言和目录。需求实现一个 getNth() 方法，传入一个链表和一个索引，返回索引代表的节点。索引以 0...

syoya 2019-08-21 14:53 评论0 收藏0
【译】JavaScript数据结构（3）：单向链表与双向链表

摘要：计算机科学中最常见的两种数据结构是单链表和双链表。双向链表双向链表具有单链表的所有功能，并将其扩展为在链表中可以进行双向遍历。双向链表的操作我们的链表将包括两个构造函数和。与单链表不同，双向链表包含对链表开头和结尾节点的引用。翻译：疯狂的技术宅英文：https://code.tutsplus.com/art...说明：本文翻译自系列文章《Data Structures With Ja...

Chiclaim 2019-08-20 18:20 评论0 收藏0
详解ahooks解决React闭包问题方法

　　想必大家都能看得懂的源码 ahooks 整体架构篇，且可以使用插件化机制优雅的封装你的请求hook，现在我们就探讨下ahooks 是怎么解决 React 的闭包问题的？。　　React 的闭包问题　　先来看一个例子：　　importReact,{useState,useEffect}from"react"; 　　exportdefault()=>{ 　　const[c...

3403771864 2022-11-06 16:51 评论0 收藏0
Map总结，看这篇就够了

摘要：继承于，实现了接口。的定义的定义从中，我们可以看出和都实现了接口。指向的的总的大小是迭代器还是枚举类的标志为，表示它是迭代器否则，是枚举类。默认加载因子指定容量大小的构造函数当的实际容量阈值时，阈值总的容量加载因子，就将的容量翻倍。概要学完了Map的全部内容，我们再回头开开Map的框架图。showImg(https://segmentfault.com/img/remote/146...

yzzz 2019-08-15 17:49 评论0 收藏0