JAVASCRIPT算法（3）

Miyang 发布于2019-08-16 10:54 / 522人阅读

摘要：首先是链表的定义语法搞错了。分析本题与编程之美上的从无头单链表中删除节点类似。但是如果节点是尾节点时，该方法就行不通了。分析非递归的算法很简单，用三个临时指针在链表上循环一遍即可。递归算法是先逆转下一个节点，再逆转当前节点。

链接描述## 面试前准备了Promise的一种实现（大致理解和写出来），二叉树的构建，删除，查找，插入，快排的非递归，准备了蛮多的吧，但是没考虑链表。然后考个链表的反转，其实很简单，只不过有点懵，比我想的稍微难了点，然后这种考虑算法的实现而忽略了特殊情况的考虑，虽然我确定我能写出来，但是在那段懵的时间没有。后来看到了我朋友写的链表面试题，链接在此。

我朋友是做Android开发的，以java的形式举了几个例子。我是眼高手低，还是练练javascript的形式吧。

首先是链表的定义
/*class Node{ //语法搞错了。
constructor(val){
this.val= val;
this.next = null;
}
}*/
function Node(val){
this.val = val;
this.next = null;
}

题目描述：给定单链表中需要删除的节点（不是尾节点），在 O(1) 时间删除该节点。

分析：本题与《编程之美》上的「从无头单链表中删除节点」类似。主要思想都是「狸猫换太子」，即用下一个节点数据覆盖要删除的节点，然后删除下一个节点。但是如果节点是尾节点时，该方法就行不通了。

function deleteNode(node){
 if(node==null||node.next==null) return ;
 node.val = node.next.val;
 node.next = node.next.next;
}

题目描述：输出一个单链表的逆序反转后的链表。

分析：非递归的算法很简单，用三个临时指针 prev、cur、next 在链表上循环一遍即可。递归算法是先逆转下一个节点，再逆转当前节点。

有点伤心的题目啊，其实还是蛮简单的，就是在改变next的指向的时候，保留next指向的节点。

function reverseByLoop(head){
     if(head == null || head.next == null) return head;
     var pre = null,
         next;
     while(head!=null){
       next = head.next;
       head.next = pre;
       pre = head;
       head = next;
     }
     return pre;
}

function reverseByRecursion(head){
  if(head==null||head.next ==null) return head;
  //递归的好难理解。。
  var headOfNext = reverseByRecursion(head.next);
  head.next.next = head;
  head.next = null;
  return headOfNext;
  
}

递归有一种给我一个支点和足够长的棍，我就能翘起地球一样的感觉。
比如原链表是这样的结构A->B->C->D->E.
既然这个function的目的是把链表倒序，那么如果我调用reverseByRecursion(B),
那么返回的结果一定是E,并且E->D->C->B.
现在我手中还有A，A->B。所以为了形成E->D->C->B->A, 只需要把B指向A,然后A指向NULL. 所以就是后续操作了。

那么还需要验证临界情况，即最里面一层执行的状态能否达成逆转链表的效果。
调用栈如下
reverseByRecursion(E)->return E;
reverseByRecursion(D)-> D.next.next=D;=>E->D D.next=NULL; return E; E->D->NULL
reverseByRecursion(C)-> C.next.next=C;=>D.next=C C.next=NULL; return E;=>E->D->C->NULL
reverseByRecursion(B)
reverseByRecursion(A)

先这样吧。果然有点眼高手低。

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

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

优秀程序员都应该学习的 GitHub 上开源的数据结构与算法项目

摘要：强烈推荐上值得前端学习的数据结构与算法项目，包含图的演示过程与视频讲解。该仓库包含了多种基于的算法与数据结构，提供进一步阅读的解释和链接。数据结构和算法必知必会的个代码实现。 showImg(https://segmentfault.com/img/bVbvpYZ); 前言算法为王。想学好前端，先练好内功，内功不行，就算招式练的再花哨，终究成不了高手；只有内功深厚者，前端之路才会走得...

cheukyin 2019-08-26 10:17 评论0 收藏0
JavaScript深入浅出第3课：什么是垃圾回收算法？

摘要：摘要是如何回收内存的深入浅出系列深入浅出第课箭头函数中的究竟是什么鬼深入浅出第课函数是一等公民是什么意思呢深入浅出第课什么是垃圾回收算法最近垃圾回收这个话题非常火，大家不能随随便便的扔垃圾了，还得先分类，这样方便对垃圾进行回收再利用。摘要： JS是如何回收内存的？《JavaScript深入浅出》系列： JavaScript深入浅出第1课：箭头函数中的this究竟是什么鬼？ Jav...

AaronYuan 2019-08-23 18:28 评论0 收藏0
常用排序算法之JavaScript实现

摘要：代码实现六堆排序算法简介堆排序是指利用堆这种数据结构所设计的一种排序算法。九计数排序算法简介计数排序是一种稳定的排序算法。计数排序不是比较排序，排序的速度快于任何比较排序算法。赞助我以写出更好的文章，give me a cup of coffee? 2017最新最全前端面试题 1、插入排序 1）算法简介插入排序（Insertion-Sort）的算法描述是一种简单直观的排序算法。它...

jerry 2019-08-21 12:27 评论0 收藏0
深入浅出 JavaScript 的 Array.prototype.sort 排序算法

摘要：快速排序是不稳定的排序算法。浏览器的实现不同有什么影响排序算法不稳定有什么影响举个例子某市的机动车牌照拍卖系统，最终中标的规则为按价格进行倒排序相同价格则按照竞标顺位即价格提交时间进行正排序。本文要解决的问题 1、找出 Array.prototype.sort 使用的什么排序算法 2、用一种直观的方式展示 Array.prototype.sort 的时间复杂度，看看它有多快？ 3、...

itvincent 2019-08-21 11:55 评论0 收藏0
【你该懂一点Javascript算法系列】之单源最短路径 - Dijkstra算法

摘要：算法系列单源最短路径算法迪杰斯特拉算法是由荷兰计算机科学家狄克斯特拉于年提出的，因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法，解决的是有向图中最短路径问题。 Javascript算法系列 - 单源最短路径 - Dijkstra算法迪杰斯特拉算法是由荷兰计算机科学家狄克斯特拉于1959年提出的，因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法，解决的是有...

SoapEye 2019-08-23 15:04 评论0 收藏0
JavaScript算法 ,Python算法,Go算法,java算法,系列之归并排序

摘要：常见的内部排序算法有插入排序希尔排序选择排序冒泡排序归并排序快速排序堆排序基数排序等。用一张图概括归并排序英语，或，是创建在归并操作上的一种有效的排序算法，效率为。常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括： showImg(https://segmentfault.com/img/bVNwuO?w=966&h=...

zhou_you 2019-08-16 10:34 评论0 收藏0