摘要:我打算写一个链表操作的系列,来自的系列,实现语言是。通过自己实现一个链表和常用操作,可以加深理解这类数据结构的优缺点。链表经常用来训练指针操作,虽然这只对适用,但等高级语言中控制引用的思路其实也差不多。
TL;DR
我打算写一个链表操作的系列,来自 Codewars 的 Linked List 系列 kata ,实现语言是 JavaScript 。这篇是开篇,简单描述了一下我写这个的目的,也作为系列的目录。
为什么要学习链表我的年度目标之一就是学习一些数据结构和算法,用于打基础和培养逻辑思维能力。Codewars 上的这个系列同时符合这两点。
链表是常用数据结构之一,它甚至是某些语言(比如 Elixir)的内置数据结构。通过自己实现一个链表和常用操作,可以加深理解这类数据结构的优缺点。
链表经常用来训练指针操作,虽然这只对 C 适用,但 JavaScript 等高级语言中控制引用的思路其实也差不多。而且链表也是练习递归的理想数据结构之一。
基于此,每个 kata 我都会尽量提供递归和循环两个版本,某些操作会实现尾递归以符合题目要求。这是一个很有意思的过程,有时候递归更好,有时候循环更好,也有少数时候两者都不是最优化的方案。
目录Codewars 上没有总纲,但每一个 kata 都有整个系列的目录。我列举如下,一共 18 个 kata 。每篇的博客链接会在更新后附上。另外,所有代码 都放在 GitHub 上,代码的更新比博客要快,如果觉得对你有帮助,请帮我点个赞!
Push & BuildOneTwoThree
Length & Count
Get Nth Node
Insert Nth Node
Sorted Insert
Insert Sort
Append
Remove Duplicates
Move Node
Move Node In-place
Alternating Split
Front back split
Shuffle Merge
Sorted Merge
Merge sort
Sorted Intersect
Iterative Reverse
Recursive Reverse
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/80974.html
摘要:需求实现一个函数对链表进行升序排列插入排序。关于插入排序插入排序的介绍可以看,大体逻辑为建立一个新的空链表。遍历完成,返回新链表。代码如下总结因为有上个的函数的帮助,这个插入排序实现起来非常简单。 TL;DR 2016 年末最后一篇,对链表进行插入排序。系列目录见 前言和目录 。 需求 实现一个 insertSort() 函数对链表进行升序排列(插入排序)。实现过程中可以使用 上一个 ...
摘要:需求实现函数进行归并排序。解法归并排序的运行方式是,递归的把一个大链表切分成两个小链表。切分到最后就全是单节点链表了,而单节点链表可以被认为是已经排好序的。这时候再两两合并,最终会得到一个完整的已排序链表。用把排好序的两个链表合并起来。 TL;DR 对链表进行归并排序,系列目录见 前言和目录 。 需求 实现函数 mergeSort() 进行归并排序。注意这种排序法需要使用递归。在 fr...
摘要:需求实现函数把两个链表合并成一个。新链表的节点是交叉从两个链表中取的。通过行的调换指针,我们可以保证下一次循环就是对另一个链表进行操作了。这样一直遍历到两个链表末尾,返回结束。参考资料的代码实现的测试 TL;DR 把两个链表洗牌合并成一个,系列目录见 前言和目录 。 需求 实现函数 shuffleMerge() 把两个链表合并成一个。新链表的节点是交叉从两个链表中取的。这叫洗牌合并。举...
摘要:需求实现一个函数,把源链表的头节点移到目标链表。当源链表为空时函数应抛出异常。为了简化起见,我们会用一个对象来存储改变后的源链表和目标链表的引用。它也是函数的返回值。解法配合,这个非常简单,注意这个函数没有改变两个链表本身。 TL;DR 把一个链表的首节点移到另一个链表。系列目录见 前言和目录 。 需求 实现一个 moveNode() 函数,把源链表的头节点移到目标链表。当源链表为空时...
摘要:需求实现函数取两个已排序的链表的交集,交集指两个链表都有的节点,节点不一定连续。每个链表应该只遍历一次。结果链表中不能包含重复的节点。当我们对比和的值时,有这几种情况,这时节点肯定交集,加入结果链表中。 TL;DR 一次遍历取两个排序链表的交集,系列目录见 前言和目录 。 需求 实现函数 sortedIntersect() 取两个已排序的链表的交集,交集指两个链表都有的节点,节点不一定...
阅读 509·2023-04-26 01:39
阅读 4406·2021-11-16 11:45
阅读 2571·2021-09-27 13:37
阅读 853·2021-09-01 10:50
阅读 3525·2021-08-16 10:50
阅读 2194·2019-08-30 15:55
阅读 2951·2019-08-30 15:55
阅读 2230·2019-08-30 14:07