资讯专栏INFORMATION COLUMN

前端校招准备系列--使用js实现链表的操作

fuyi501 / 3263人阅读

摘要:思路查找倒数第个节点,可以看做是查找正序第个节点可以根据第一题的结果取数组的第个节点使用思路输入一个链表,反转链表后,输出新链表的表头。

前言

  在写项目的时候会发现,并没有使用很多关于链表的东西,大多数情况使用的都是数组,但是由于在准备校招,很多公司都会考到这个问题,所以准备对链表的相关操作进行总结,并对其中的重难点进行强调,最后还会附加几道关于链表的算法题,那么现在就开始吧!

链表的基础操作 创建一个链表结构

  了解过链表的同学应该都知道,链表有几个特点:

可以动态扩展空间(在js中,数组也是这样的,但是有的语言中数组的长度是固定的,不能动态添加,如c语言)

需要一个头节点

需要知道下一个节点的地址

  可以将链表中的每个节点看成是一个对象,这个对象中有两个属性,一个是该节点的值,一个是该节点的下一个节点的地址(如果是双链表,还要添加前一个节点地址的属性)

</>复制代码

  1. function LinkedList(){
  2. //辅助类:表示要加入链表的项
  3. let node = function(element){
  4. this.element = element;
  5. this.next = null;//这个节点的下一个节点暂时为空
  6. }
  7. let length = 0;
  8. let head = null;
  9. this.append() = function(element){};//向链表的尾部添加节点
  10. this.insert() = function(position,element){};//在指定的位置添加节点
  11. this.remove = function(element){};//将指定的节点删除掉
  12. this.removeAt = function(position){};//将指定位置的节点删除
  13. this.searchElement = function(element){};//查找指定元素的位置
  14. this.searchPosition = function(position){};//查找指定位置的元素
  15. }

  上面代码中包含了很多要实现的操作,包括最基本的增删以及查询。下面我们就来一一的实现上面列举的方法:

实现增加节点的操作

在尾节点处添加节点

</>复制代码

  1. function append(element){
  2. let node = new Node(element);//1
  3. let current;//2
  4. //3
  5. if(head === null){
  6. head = node
  7. }else{
  8. current = head
  9. while(current.next){
  10. current = current.next
  11. }
  12. current.next = node
  13. }
  14. length++;//4
  15. }
代码分析:

根据传入的元素定义一个节点,该元素作为这个节点的值

定义一个变量表示当前的节点

判断是否含有头节点,如果没有头节点,说明链表中还没有值,将传进来的这个值作为头节点;否则,对链表进行遍历,找到最后一个节点,将其next属性赋值为新增的节点

链表的长度+1

在任意位置添加节点

分析

  将这个位置的前一个节点的next属性赋值为这个节点,并将它原先的下一个节点保存下来,赋值给现在这个节点的next属性

</>复制代码

  1. function insert(position,element){
  2. if(position >=0 && position <= length){
  3. //当position为length时,表示在尾节点处添加,包含了append方法
  4. let node = new Node(element);
  5. let current = head;
  6. let previous;//当前节点的前一个节点,在position处添加节点,就是在previos和current之间添加
  7. if(position = 0){
  8. node.next = head;
  9. head = node;
  10. }else{
  11. for(let i = 0;i< position;i++){
  12. pervious = current;
  13. current = current.next;
  14. }
  15. pervious.next = node;
  16. node.next = current;
  17. }
  18. length++;
  19. return true;
  20. }else{
  21. return false;
  22. }
  23. }
代码分析:

检查postion是否越界,若没有越界,则创建一个节点

定义一个变量表示当前的节点,初始化为头节点,表示从头节点开始遍历;一个变量表示当前节点的前一个节点,作用是插入节点时方便找到前一个节点

判断是否在头节点前添加,如果是就将头节点赋给node的next属性,并且头节点改为这个节点;否则,遍历出这个位置的节点,将该节点插入到这个位置的节点前面

链表的长度+1

实现删除节点的操作

  基本思路:删除节点的操作就是将目标节点前面的那个节点的指针指向目标节点的有一个节点

删除指定节点

</>复制代码

  1. function removed(element){
  2. let node = new Node(element);
  3. let pervious;
  4. let nextNode;
  5. let current = head;
  6. if(head != null){
  7. while (current != node){
  8. pervious = current;
  9. current = current.next;
  10. nextNode = current.next;
  11. }
  12. pervious.next = nextNode;
  13. length--;
  14. return true;
  15. }else{
  16. return false;
  17. }
  18. }
代码分析:重点在于抓住需要哪些节点,并且进行这个操作需要改变什么,判断条件是怎样的

删除指定位置的节点

</>复制代码

  1. function removedAt(position){
  2. //判断所给位置是否溢出
  3. if(position > -1 && position < length){
  4. let current = head;
  5. let pervious;
  6. let nextNode;
  7. let i = 0;
  8. while(i < position){
  9. pervious = current;
  10. current = current.next;
  11. nextNode = current.next;
  12. }
  13. pervious.next = nextNode;
  14. length--;
  15. return true;
  16. }else{
  17. return false;
  18. }
  19. }
实现查询节点的操作

  其实查询节点和删除节点差不多,都是通过遍历,找到相应的节点或是相应的位置,然后进行操作,说起来比删除节点还要简单

查询某个位置是哪个节点

</>复制代码

  1. function searchElement(element){
  2. //输入元素,找到该元素后返回该元素的位置
  3. if(head != null){
  4. let node = new Node(element);
  5. let current;
  6. let index = 0;
  7. if(head == node){
  8. return 0;
  9. }else{
  10. current = head;
  11. while(current != node){
  12. current = current.next;
  13. index++;
  14. }
  15. return index;
  16. }
  17. }else{
  18. return -1;
  19. }
  20. }

查询某个节点是在哪个位置

</>复制代码

  1. function searchPosition(position){
  2. //查找某一个位置的元素是什么
  3. if(position > -1 && position < length){
  4. let i = 0;
  5. let current = head;
  6. while(i< position){
  7. current = current.next;
  8. i++;
  9. }
  10. return current;
  11. }else{
  12. return null;
  13. }
  14. }
思路总结

  关于链表的操作还有很多,复杂一点的链表还有双链表(在初始化节点的时候增加一个前节点)和循环链表(尾节点的下一个节点是头节点),这些链表的操作也是可以使用js实现的,这里就不多说了。总结一下,链表的核心在于

链表中节点可看做一个对象,有两个属性值,一个是节点值,一个是指针

链表的增删就是改变指针指向

链表查找时,重点是current = current.next

有关链表的算法题

  这里总结几道在牛客网上的剑指offer中刷到的几道关于链表的算法题,这些题在笔试中还是很有可能遇到的,接着往下看吧!

1. 输入一个链表,按链表值从尾到头的顺序返回一个ArrayList。

  思路:(1)将链表值从头到尾输出到一个数组中,然后将这个数组进行反转得到ArrayList
        (2)使用数组的unshift方法,将链表值倒序放进数组
        (3)先使用栈存放顺序遍历的结果,利用栈先进后出的特性,出栈的时候用数组保存

</>复制代码

  1. //使用思路2的方法
  2. function Node(element){
  3. this.val = element
  4. this.next = null
  5. }
  6. function logList(head){
  7. if(head != null){
  8. let ArrayList = [];
  9. while(head){
  10. ArrayList.unshift(head.element);
  11. head = head.next;
  12. }
  13. return ArrayList;
  14. }else{
  15. return [];
  16. }
  17. }

2. 输入一个链表,输出该链表中倒数第k个结点。

  思路:(1)查找倒数第k个节点,可以看做是查找正序第length-k个节点
        (2)可以根据第一题的结果取数组的第k-1个节点

</>复制代码

  1. //使用思路2
  2. function Node(element){
  3. this.element = element;
  4. this.next = null;
  5. }
  6. function FindKthToTail(head, k)
  7. {
  8. let array = []
  9. while(head != null){
  10. array.unshift(head)
  11. head = head.next;
  12. }
  13. return array[k-1];
  14. }

3. 输入一个链表,反转链表后,输出新链表的表头。

  思路:把倒序后的链表放进一个数组中,然后将这个数组的每一位的next属性指向下一位

</>复制代码

  1. function ListNode(x){
  2. this.val = x;
  3. this.next = null;
  4. }
  5. function ReverseList(pHead)
  6. {
  7. if(pHead){
  8. let arr = [];
  9. while(pHead){
  10. arr.unshift(pHead);
  11. pHead = pHead.next;
  12. }
  13. for(let i =0;i< arr.length;i++){
  14. arr[i].next = arr[i+1]
  15. }
  16. return arr[0]
  17. }
  18. }
    本人的水平不佳,可能有些地方写错了,欢迎在评论中指出,大家一起进步哟!

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

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

相关文章

  • 如何准备校招技术面试

    摘要:网易跨境电商考拉海购在线笔试现场技术面面。如何看待校招面试招聘,对公司而言,是寻找劳动力对员工而言,是寻找未来的同事。 如何准备校招技术面试 标签 : 面试 [TOC] 2017 年互联网校招已近尾声,作为一个非 CS 专业的应届生,零 ACM 经验、零期刊论文发表,我通过自己的努力和准备,从找实习到校招一路运气不错,面试全部通过,谨以此文记录我的校招感悟。 写在前面 写作动机 ...

    MkkHou 评论0 收藏0
  • 初级前端开发面试总结

    摘要:前端面试总结先说背景,本人年月毕业,去年十月校招到今年月一直在做前端开发工作,年前打算换工作,就重新梳理下面试考点总结包含基础,基础,常见算法和数据结构,框架,计算机网络相关知识,可能有的点很细,有的点很大,参考个人情况进行总结,方便对知识 前端面试总结 先说背景,本人2018年7月毕业,去年十月校招到今年10月一直在做前端开发工作,年前打算换工作,就重新梳理下面试考点总结包含: ...

    jifei 评论0 收藏0
  • 初级前端开发面试总结

    摘要:前端面试总结先说背景,本人年月毕业,去年十月校招到今年月一直在做前端开发工作,年前打算换工作,就重新梳理下面试考点总结包含基础,基础,常见算法和数据结构,框架,计算机网络相关知识,可能有的点很细,有的点很大,参考个人情况进行总结,方便对知识 前端面试总结 先说背景,本人2018年7月毕业,去年十月校招到今年10月一直在做前端开发工作,年前打算换工作,就重新梳理下面试考点总结包含: ...

    tigerZH 评论0 收藏0
  • 阿里校招前端面经

    摘要:的回调函数执行的优先级要高于,属于观察者。的回调函数保存在一个数组中,会将异步回调放到当前帧的末尾回调之前,如果过多,会导致回调不断延后最后堆积太多。 阿里一面是电话面,问得不多,但是挺有深度。面试官一开始就说,看了你的项目,觉得你基础挺好的,那我就不问基础了。然后全程就真的没有问一个基础问题。。 1.说说你做的那个网页版手机QQ项目的难点。 我首先想到了滚动条位置无法还原的问题,也就...

    ccj659 评论0 收藏0
  • javascript链表实现

    摘要:而遍历链表,则是跟着首元素一直遍历至尾元素。单链表代码实现类实现类用来设置链表的节点相关信息本节点信息指向下一个节点的指针类实现类实现的是一些对链表进行操作的方法,包括插入删除节点查找节点等。 单链表初识 链表是由一组节点组合成的集合.每个节点都使用一个对象的引用指向它的后继,指向另一个节点的引用叫做链 数组元素靠他们的位置进行引用,链表元素则是靠相互之间的关系进行引用,在下图中bre...

    Imfan 评论0 收藏0

发表评论

0条评论

最新活动
阅读需要支付1元查看
<