JAVASCRIPT算法（4）

GraphQuery 发布于2019-08-21 17:54 / 638人阅读

摘要：继续学习链表的算法链接题目描述删除单链表倒数第个节点，，尽量在一次遍历中完成。如果条件是，那么被删除的点就是，但是这样删不掉。思路很相似，那么三分之一，四分之一，五分之一，或者均分三段，均分四段也是类似的想法。

继续学习链表的算法链接

题目描述：删除单链表倒数第 n 个节点，1 <= n <= length，尽量在一次遍历中完成。

分析：看到题目时的第一想法是先遍历一次计算出单链表的长度 length，然后在遍历第二次删除第 length - n + 1 个节点，但是这需要遍历两次。正常的删除第 n 个节点只需要遍历一次就可以，如何只遍历一次找到倒数第 n 个节点呢？可以设置两个指针 p1、p2，首先 p1 和 p2 都指向 head，p2 移动到第 n 个节点，然后 p1 和 p2 同时向后移动，当 p2 移动到末尾时，p1 刚好指向倒数第 n 个节点。因为最后要删除倒数第 n 个节点，所以可以找到倒数第 n + 1 个节点，方便删除节点。这种思想在学校的时候学习过，还是蛮有用的吧，还是可以学到很多东西的，只不过总是找了很多借口。

 function Node(val){ //class的定义好像有点没弄好
     this.val = val;
     this.next = null;
   }
    
   function removeNthNodeFromEnd(head, location){
     if(head == null) return head;
     var pointer1 = head;
     var pointer2 = head;
     for(var i = 0 ; i < location; i ++ ){
       pointer2 = pointer2.next;
       if(pointer2==null&&i!=location-1)
       return null; //如果根本没有n个元素，就没有倒数第n个元素
     }
     if(pointer2==null){  //总共就n个元素，那么head就是要删除的那个点，返回下一个节点作为头节点就好了。
       return pointer1.next;
     }
     while(pointer2.next!=null){ //如果条件是pointer2!=null，那么被删除的点就是pointer1，但是这样删不掉。所以应该记录要删除的节点的上一个节点。
       pointer2=pointer2.next;
       pointer1=pointer1.next;
     }
     pointer1.next = pointer1.next.next;//
     return head;

   }

我自己测试了下，测试用例如下，可能构建链表的过程有点傻。

   var head = new Node("head");
   var current = head,next = null;
   for(var i =5 ; i >0 ; i--){
     next = new Node(i);
     current.next = next;
     current = next;
   }
   function showLinkedNode(head){
     if(head==null) console.log("head is "+head);
     while(head!=null){
       console.log(head.val);
       head = head.next;
     }
   }
    showLinkedNode(head);
    var result = removeNthNodeFromEnd(head,6);
    showLinkedNode(result);

结果是 head 5 4 3 2 1 和 5 4 3 2 1
如果removeNthNodeFromEnd(head,7)，返回的是null。

   showLinkedNode(head);
   var result = removeNthNodeFromEnd(head,3);
   showLinkedNode(result);

结果是head 5 4 2 1
还是得自己动手写写，可能以前能懂，但是过了一段时间以后就不懂了，让往日的自己和后面的自己隔着时间对话。人并不总是在进步，每一个时间点的思考以及结论都很有意义。

类似的问题
题目描述：求单链表的中间节点，如果链表的长度为偶数，返回中间两个节点的任意一个，若为奇数，则返回中间节点。

分析：这道题的思路和第 3 题「删除单链表倒数第 n 个节点」很相似。如果要求只能遍历一遍链表的花，也通过两个指针来完成。两个指针从头节点开始，慢指针每次向后移动一步，快指针每次向后移动两步，直到快指针移动到尾节点时，慢指针移动到中间节点。思路很相似，那么三分之一，四分之一，五分之一，或者均分三段，均分四段也是类似的想法。

  function findMiddleNode(head){
     if(head==null||head.next==null) return head;
     var fastPoint = head;
     var normalPoint = head;
     while(fastPoint!=null&&fastPoint.next!=null){
           fastPoint = fastPoint.next.next;
           normalPoint = normalPoint.next;
     }
     return normalPoint;
   }

这个感觉比较简单。

云服务器专线服务 javascript算法题 android 4 4 短信安卓4 4 网页缩放 android 模拟器 4 4

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

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

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

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

cheukyin 2019-08-26 10:17 评论0 收藏0
【你该懂一点Javascript算法系列】之单源最短路径 - Dijkstra算法

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

SoapEye 2019-08-23 15:04 评论0 收藏0
JavaScript 数据结构与算法之美 - 冒泡排序、插入排序、选择排序

摘要：之所以把冒泡排序选择排序插入排序放在一起比较，是因为它们的平均时间复杂度都为。其中，冒泡排序就是原地排序算法。所以冒泡排序是稳定的排序算法。选择排序思路选择排序算法的实现思路有点类似插入排序，也分已排序区间和未排序区间。 showImg(https://segmentfault.com/img/bVbuvnj?w=900&h=250); 1. 前言算法为王。想学好前端，先练好内功，...

canger 2019-08-26 10:15 评论0 收藏0
JavaScript设计模式----策略模式

摘要：实际上在这种将函数作为一等对象的语言里，策略模式已经融入到了语言本身当中，我们经常使用高阶函数来封装不同的行为，并且把它传递到另一个函数中。声明：这个系列为阅读《JavaScript设计模式与开发实践》 ----曾探@著一书的读书笔记 1.策略模式的定义将不变的部分和变化的部分隔开是每个设计模式的主题。定义一系列的算法，把它们一个个封装起来，并且使它们可以相互替换。 2.策略模式...

forrest23 2019-08-21 10:56 评论0 收藏0
JavaScript 数据结构与算法之美 - 十大经典排序算法汇总

摘要：笔者写的数据结构与算法之美系列用的语言是，旨在入门数据结构与算法和方便以后复习。这应该是目前较为简单的十大经典排序算法的文章讲解了吧。比如原本在的前面，而，排序之后，在的后面十大经典排序算法冒泡排序思想冒泡排序只会操作相邻的两个数据。 showImg(https://segmentfault.com/img/bVbvHet); 1. 前言算法为王。想学好前端，先练好内功，内功不行，就...

zsy888 2019-08-26 10:27 评论0 收藏0
JavaScript中的算法（附10道面试常见算法题解决方法和思路）

摘要：中的算法附道面试常见算法题解决方法和思路关注每日一道面试题详解面试过程通常从最初的电话面试开始，然后是现场面试，检查编程技能和文化契合度。值得记住的数组方法有和。一个好的解决方案是使用内置的方法。 JavaScript中的算法（附10道面试常见算法题解决方法和思路）关注github每日一道面试题详解 Introduction 面试过程通常从最初的电话面试开始，然后是现场面试，检查编程...

Cruise_Chan 2019-08-26 10:22 评论0 收藏0