天津做网站哪家服务好,域名请记住222922,做网站怎么跟别人讲价,网络营销课程总结ppt【JavaScript】leetcode链表相关题解 一、什么是链表#xff1f;二、Javascript中的链表三、leetcode相关链表2.两数相加237.删除链表中的节点206.反转链表 #x1f48e;个人主页: 阿选不出来 #x1f48e;个人简介: 大三学生#xff0c;热爱Web前端#xff0c;随机掉落学… 【JavaScript】leetcode链表相关题解 一、什么是链表二、Javascript中的链表三、leetcode相关链表2.两数相加237.删除链表中的节点206.反转链表 个人主页: 阿选不出来 个人简介: 大三学生热爱Web前端随机掉落学习碎片 目前开发的专栏: JS VueReact 祝愿今天的你比昨天更加博识了 一、什么是链表
链表的官方定义链表是一种物理存储单位上非连续、非顺序的存储结构数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
看到这里相信你肯定一知半解。没关系接下来我们将链表与我们熟悉的数组进行一个对比就好理解多了
存储数据方面
数组使用一块连续的内存空间地址存放数据
链表使用不连续的内存地址存放数据
在存储数据方面链表相较数组更加自由节省内存资源更利于内存空间的利用率。
元素的查找
数组每个元素都有其对应的索引可以直接通过索引访问值
链表链表没有索引每个链表节点至少由两部分组成值指向下一个节点的指针。链表的查找只能从头结点开始顺着各个节点的指针查找。
功能
数组与链表都能实现基本的增删改查功能。
二、Javascript中的链表
在JavaScript的数据结构中并不存在链表这一类型但是我们可以使用Object模拟链表。
链表的常用操作
新增节点 append | 删除节点 remove | 插入节点 insert | 获取索引 indexOf | 链表转字符换 toString | 获取链表长度 size | 获取链表是否为空 isEmpty
手撕单向链表
class Node {constructor(element){// 保存元素this.element element;// 指向下一个节点this.next null;}
}class LinkedList {// 构造器constructor() {this.head null;this.length 0;}append(element) {const newNode new Node(element)let node this.get(this.length - 1)if(node){node.next newNode}else{this.head newNode} this.length}insert(position, element) {if(position 0 || position this.length) return false;let newNode new Node(element)let prenode this.get(position - 1)if(prenode){newNode.next prenode.nextprenode.next newNode}else{newNode.next this.headthis.head newNode}this.length}get(position) {if(typeof position ! number || position 0 || position this.length - 1)return null;let index 0let position_node this.headwhile(index position){position_node position_node.next}return position_node}indexOf(element) {let index 0let index_node this.headwhile(index_node){if(index_node.element element){return index}index;index_node index_node.next}return -1}update(positon, element) {if(positon 0 || positon this.length - 1) return;const result this.removeAt(positon)this.insert(positon, element)return result}removeAt(position) {if(position 0|| position this.length - 1) return;const prenode this.get(position - 1)const current prenode ? prenode.next : this.headif(prenode) {if(position this.length - 1){prenode.next null}else{prenode.next prenode.next.next} }else{this.head this.head.next}this.length--return current.element;} remove(element){const index this.indexOf(element) if(index -1) return;this.removeAt(index)}isEmpty(){return this.length 0}size(){return this.length}toString(){let next_node this.headlet string while(next_node){string string next_node.element.toString()next_node next_node.next}return string}
}手撕双向链表
// 双向链表
class DoublyNode extends Node {constructor(element){super(element);this.prev null}
}class DoublyLinkedList extends LinkedList {constructor(){super();this.tail null;}// 追加append(element){let node new DoublyNode(element)if(this.headnull){this.head node;this.tail node}else{node.prev this.tailthis.tail.next nodethis.tail node}this.length}// 插入节点insert(position, element){if(position0 || position this.length) return;const newNode new DoublyNode(element)let node this.get(position)if(position0){this.head newNodenewNode.next nodenode.prev newNode }else if(positionthis.length){newNode.prev this.tailthis.tail.next newNodethis.tail newNode}else {newNode.prev node.prevnode.prev.next newNodenewNode.next nodenode.prev newNode }this.length}// 获取节点get(position){if(position0 || positionthis.length - 1)return falseif(position this.length/2){let i 0let node this.headwhile(i position){node node.next}return node}else{let i this.length - 1let node this.tailwhile(i-- position){node node.prev}return node}}// 删除节点removeAt(position){if(position0 || position this.length - 1) return;const node this.get(position)if(position 0){if(this.length 1){this.head null;this.tail null}else{this.head node.nextnode.next.prev null}}else if(position this.length - 1) {this.tail node.prevnode.next nullnode.prev.next null}else {node.prev.next node.nextnode.next.prev node.prev}this.length--}
}三、leetcode相关链表
2.两数相加
题目描述
给你两个 非空 的链表表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的并且每个节点只能存储 一位 数字。
请你将两个数相加并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外这两个数都不会以 0 开头。
示例 输入l1 [2,4,3], l2 [5,6,4] 输出[7,0,8] 解释342 465 807. 提示
每个链表中的节点数在范围 [1, 100] 内0 Node.val 9题目数据保证列表表示的数字不含前导零
题解
遍历这两个链表逐位相加如果有进位就将目标链表下一位的节点值设为进位值并与两个链表的下一位值相加。
/*** Definition for singly-linked list.* function ListNode(val, next) {* this.val (valundefined ? 0 : val)* this.next (nextundefined ? null : next)* }*/
/*** param {ListNode} l1* param {ListNode} l2* return {ListNode}*/
var addTwoNumbers function(l1, l2) {let l3 num new ListNode(0)while(l1 || l2){n1 l1 ? l1.val : 0n2 l2 ? l2.val : 0// 两数相加 进位数let sum n1 n2 num.valif(l1){l1 l1.next}if(l2){l2 l2.next}num.val sum % 10if(l1 || l2 || Math.floor(sum / 10)){num.next new ListNode(Math.floor(sum / 10))}num num.next}return l3
};237.删除链表中的节点
题目描述
有一个单链表的 head我们想删除它其中的一个节点 node。给你一个需要删除的节点 node 。你将 无法访问 第一个节点 head。链表的所有值都是 唯一的并且保证给定的节点 node 不是链表中的最后一个节点。
删除给定的节点。注意删除节点并不是指从内存中删除它。这里的意思是
给定节点的值不应该存在于链表中。链表中的节点数应该减少 1。node 前面的所有值顺序相同。node 后面的所有值顺序相同。 输入head [4,5,1,9], node 5 输出[4,1,9] 解释指定链表中值为 5 的第二个节点那么在调用了你的函数之后该链表应变为 4 - 1 - 9 解题思路
删除节点的一般思路为找到要删除节点的上一节点改变上一节点的next指针。但在本题中deleteNode函数只提供了node节点 [即要删除的节点且无法访问head只能访问node之后的节点]因此我们无法找到上一节点。
我们可以用node的下一个节点替换当前节点node这样在整个链表中node也就被删除了。
var deleteNode function(node) {node.val node.next.val node.next node.next.next
};206.反转链表
题目描述
给你单链表的头节点 head 请你反转链表并返回反转后的链表。
示例 输入head [1,2,3,4,5] 输出[5,4,3,2,1] 解题思路
设置一个prev空链表 [保存已经逆向的链表] 和 last 待处理链表修改每一个节点的指针使指针指向上一节点。
var reverseList function(head) {let prev null;let last head;while(last){const next last.nextlast.next prevprev lastlast next}return prev
}链表相关试题未完续…
