JS刷力扣-链表【持续跟新】
发布时间
阅读量：
阅读量
力扣的链表归类
2.两数相加【链表+递归】
前置知识：
1. 链表是一种由指针串联而成的一维数据结构；每个节点由两个字段组成；一个是存储数据的内容域（Data Field），另一个是存储指向下一个节点地址的指针域（Link Field）；尾部节点的指针字段设为空值（Null）。
2. 链表的数据操作通常从头结点开始进行；为了便于操作并简化逻辑实现；我们在链表头部设置一个附加的头结点；这个特殊的起点称为链表的头结点；有时也称作head-node或head pointer
在LeetCode练习中 new Listnode()相当于初始化了一个空值的链表
创建一个节点值为空的链表let dummy = new ListNode()等价于定义了一个空链表
定义一个节点值非空的链表xx = new ListNode(val)
a. 获取当前节点的值xx.val
b. 更新当前节点指向下一个节点xx = xx.next
思路：
初始化carry变量用于记录进位；创建sum变量用于计算总和。
生成一个新的链表结构，在其头部附加一个dummy头结点以占位；每当新增一个数据节点时就将当前指针向前移动一位。
确定两链表之和为个位或两位数：若超过10，则通过取模运算获得个位数值，并用整除运算更新carry值。
下次计算时需加入carry值并置其为零。
完成所有操作后还需最后一次检查carry：若其值为零则结束流程；否则添加数值为一的新节点至尾部。若存在该数值，则返回结果；否则在哈希集合中存入当前数值及其索引。（此处主要依据map.has()函数判断键的存在性）
/** * Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/** * @param {ListNode} l1
* @param {ListNode} l2
* @return {ListNode}
*/
var addTwoNumbers = function(l1, l2) {
// 生成一个新的链表节点 头部之前指向dummy dummy用来占位
let dummy = new ListNode()
// 创建一个用来遍历链表的变量 cur
let cur = dummy
// 生成一个用来存放进位的变量
let carry = 0
// 判断 输入的两个链表都非空
while(l1 !== null || l2 !== null){
let sum = 0 // 用来统计两个链表的和
// 判断两个链表都非空 非空则用sum加上
if(l1 !== null){
sum += l1.val
l1 = l1.next
}
if(l2 !== null){
sum += l2.val
l2 = l2.next
}
sum += carry
// 首先除10取余 让cur的下一个节点值为全部相加后的个位数
// 然后除10并向下取整 carry存放有没有进位
// 最后让cur指向下一个节点
cur.next = new ListNode(sum % 10)
carry = Math.floor(sum/10)
cur = cur.next
// console.log(dummy.next) //[7] [7,0] [7,0,8]
}
if(carry > 0){
cur.next = new ListNode(carry)
}
return dummy.next
// console.log(dummy.next) [7,0,8]
};
javascript
链表+双指针
链表+双指针
链表+双指针
前置问题
- 单向链表仅能从前到后进行遍历。
- 可以用链表长度减去n加一来确定待删结点的前一个位置。然而由于链表长度未知，则需通过遍历整个链表来计算其总长度。进一步实现一次完整扫描来解决此问题。
/** * Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/** * @param {ListNode} head
* @param {number} n
* @return {ListNode}
*/
var removeNthFromEnd = function(head, n) {
// 定义一个dummy节点 避免出现链表长度为1并且n也为1时无法处理的情况
let dummy = new ListNode()
dummy.next = head
// 让n1和n2两个指针都指向dummy
let n1 = dummy
let n2 = dummy
// // 让n2领先n1 n+1个身位的情况 就是当n2指向空结点了 n1指向要删掉的结点的前一个结点 下一步让当前n1等于n1.next.next
// for(let i = 0; i <=n; i++){
// n2 = n2.next
// }
// while(n2 !== null){
// n1 = n1.next
// n2 = n2.next
// }
// 让n2领先n1 n个身为的情况 就是当n2.next指向空结点了 n1指向要删掉的结点的前一个结点
for(let i = 0; i <n; i++){
n2 = n2.next
}
while(n2.next !== null){
n1 = n1.next
n2 = n2.next
}
// n2为null之后 n1指向的就是n的前一位
n1.next = n1.next.next
return dummy.next
};
javascript
21.合并两个有序链表【链表+递归】
/** * Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/** * @param {ListNode} list1
* @param {ListNode} list2
* @return {ListNode}
*/
var mergeTwoLists = function(list1, list2) {
// 创建一个新的链表的头结点 dummy是几乎链表题都要出现的
let curr = new ListNode()
let dummy = curr
// 当两个链表都不为空时，比较大小，然后把对应值加到curr节点后面并且移动curr当前指向的结点
while(list1 !== null && list2 !== null){
if(list1.val < list2.val){
// 这里是把list1整个都给到curr.next了，但是因为要排序所以要在for循环里不停调整节点的指向
curr.next = list1
list1 = list1.next
// console.log(curr,list1) [1,1,2,4] [2,4] ;[1,2,4] [4]
}else{
curr.next = list2
list2 = list2.next
}
curr = curr.next
}
// 其中一个链表为空时 直接把另一个不为空的链表加在后面
if(list1 !== null){
curr.next = list1
}
if(list2 !== null){
curr.next = list2
}
return dummy.next
};
javascript
24.两两交换链表中的节点【链表】
重点是这六步 交换的顺序按照链表顺序来 先改变curr指向；再改变n1指向；再改变n2指向
let n1 = curr.next
let n2 = curr.next.next
curr.next = n2
n1.next = n2.next
n2.next = n1
curr = n1
javascript /** * Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/** * @param {ListNode} head
* @return {ListNode}
*/
var swapPairs = function(head) {
let dummy = new ListNode()
dummy.next = head
let curr = dummy
while(curr.next !== null && curr.next.next !== null){
let n1 = curr.next
let n2 = curr.next.next
curr.next = n2
n1.next = n2.next
n2.next = n1
curr = n1
}
return dummy.next
};
javascript
链表
链表
/** * Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/** * @param {ListNode} head
* @return {ListNode}
*/
var deleteDuplicates = function(head) {
let current = head
while(current !== null && current.next !== null){
if(current.val === current.next.val){
current.next = current.next.next
}else{
current = current.next
}
}
return head
};
javascript
链表、双指针
链表、双指针
链表、双指针
列表结构与双指针算法
/** * Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/** * @param {ListNode} head
* @return {ListNode}
*/
var deleteDuplicates = function(head) {
let dummy = new ListNode()
dummy.next = head
let cur = dummy
while(cur.next && cur.next.next) {
if (cur.next.val === cur.next.next.val) {
const x = cur.next.val
while(cur.next && cur.next.val === x) cur.next = cur.next.next
}else {
cur = cur.next
}
}
return dummy.next
};
javascript
链表 递归
链表 递归算法
链表 递归算法
在解决链表相关问题时,通常的核心手段是操作指针.然而,如果想要通过栈的先进后出特性来实现链表的反转,则需要额外开辟一个与原链表等长的数组来存储反转后的数据.这种方案虽然能够完成任务,但其空间复杂度为O(n),其中n为链表长度.
- 通过三个指针变量prev、curr、next来完成相关操作。
- 在操作过程中，默认情况下prev始终位于current节点的前驱位置。
- 在循环中：
a. 首先将当前节点current的下一个节点（即current.next）向后移动一位。
b. 然后将current.next指针从原来的null设置为上一个被修改过的prev值。
c. 接着将上一步骤中的prev值向前迁移一位。
d. 最后更新current节点为当前被修改过的状态。 - 所有prev与next的操作均以当前节点current为基准进行。
- 为了确保数据结构的一致性，在每次操作时会优先将current节点的下一个位置设置为已存在的状态。
- 整个过程主要包括四个关键步骤：
a) 初始化阶段：设置初始状态并分配空间
b) 循环遍历阶段：执行一系列逻辑运算
c) 更新阶段：完成所有数据字段的操作
d) 终止阶段：释放资源并完成整体任务
next = curr.next
curr.next = prev
prev = curr
curr = nexr
javascript /** * Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/** * Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/** * @param {ListNode} head
* @return {ListNode}
*/
var reverseList = function(head) {
let curr = head
let prev = null
let next = head
while(curr !== null){
// es6解构赋值的新写法 这种写法不再需要next作为临时值
// 因为这种结构赋值是同一时间操作完的 所以他不需要中间变量
[curr.next, prev, curr] = [prev, curr, curr.next]
// [curr.next, curr, prev] = [prev, curr.next,curr]
// // 传统写法
// next = curr.next
// curr.next = prev
// prev = curr
// curr = next
}
return prev
};
javascript
92 翻转链表（Hard）
反转链表I的基础上又多加了两个指针用来标记位置
/** * Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/** * @param {ListNode} head
* @param {number} left
* @param {number} right
* @return {ListNode}
*/
var reverseBetween = function(head, left, right) {
let prev = null
let curr = head
let next = head
// for循环让他们都到达开始得位置
for(let i = 1; i < left; i++){
prev = curr
curr = curr.next
}
// 让这两个指针占住后续重新连接链表得关键位置
let curr2 = curr
let prev2 = prev
// 像反转链表I一样对要操作的部分进行反转
for(let i = left;i <= right; i++){
next = curr.next
curr.next = prev
prev = curr
curr = next
}
// 判断以下是不是从第一个结点就开始进行链表反转的
if(prev2 !== null){ //m > 1
prev2.next = prev
}else{
head = prev
}
curr2.next = curr
return head
};
javascript
全部评论 (0)
还没有任何评论哟~