JS刷力扣-链表【持续跟新】

力扣的链表归类

2.两数相加【链表+递归】

前置知识：
1. 链表是一种通过指针串联在一起的线性结构，每一个节点由两部分组成，一个是数据域一个是指针域（存放指向下一个节点的指针），最后一个节点的指针域指向null（空指针的意思）。
2. 链表的入口节点称为链表的头结点也就是head。

leetcode里 new Listnode()就是定义一个空节点的链表
定义一个节点值为空的链表let dummy = new ListNode()节点值为空也相当于是定义了一个空链表
定义一个节点值非空的链表xx = new ListNode(val)
a. 取链表的当前值xx.val
b. 取之后的值：当前值之后的那个值赋值给当前的值xx = xx.next

思路：

1. 定义一个变量carry用来存储进位；定义一个sum变量
2. 两链表相加要生成一个新的链表，新的链表的头部创建一个dummy节点用来占位（两个节点相加会生成一个新的节点，新的节点需要一个头部然后剩下的节点就可以一个个串在后面）
3. 让最初的curr节点指向dummy节点；没相加生成一个新的节点curr往前进一位
4. 判断两个链表相加得到的是个位数还是两位数；大于10则对sum取余sum%10得到个位数，然后将sum除10并向下取整Math.floor(sum/10)后的值赋给carry（这一步每次都要进行）
5. 两个链表的下一次相加要再加上carry，然后将carry置为0
6. 这一系列操作完成后还需要最后再检查一次carry，如果值为0则不用操作，如果值不为0要在新链表最后再加一个节点值为1
   有则返回结果
   没有则把num[i]当做key，i当做value放入map中
   （这里主要是因为使用map.has()进行判断的时候判断的是key是否存在，所以把num[i]当作key放入才能判断有没有这个元素，其次get()返回的是value，这样反着存，得到的就是num[i]的下标）

/**
 * 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]
};

19.删除链表的倒数第 N 个结点【链表+双指针】

前置问题

1. 单向链表只能从前往后遍历
2. 可以用链表长度-n+1知道要删除的结点正向的位置，但链表长度未知，可以遍历计数得到其长度，进阶尝试一次扫描完成题目

/**
 * 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
};

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
};

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

/**
 * 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
};

83.删除排序链表中的重复元素【链表】

/**
 * 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
};

82. 删除排序链表中的重复元素 II【链表、双指针】

/**
 * 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
};

206.反转链表【链表 递归】

链表相关的题大部分都是操作指针
可以借助栈后进先出的特点实现反转，但是需要多开一个数组，会占据O(n)空间
思路

1. 用三个指针实现 prev、curr、next
2. prev永远指向curr和next的前一个，curr和next开始指向同一个结点；
3. for循环遍历，先让next后移，然后让curr.next指针指向prev，然后将prev迁移，最后让curr也指向next
4. 由于prev和next的操作都是基于curr的位置来实现，所以第一步是改变next；第二步是改变prev；最后才能改变curr
5. next在这里的作用主要是先占据curr.next的那个位置后边再接curr过来。
6. 主要的四步

next = curr.next
curr.next = prev
prev = curr
curr = nexr

/**
 * 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
};

92 反转链表II

反转链表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
};