# 链表

# 数组 vs 链表

数组：增删非首尾元素时往往需要移动元素
链表：增删非首尾元素，不需要移动元素，只需要更改 next 的指向即可

# JS 中的链表

JavaScript 中没有链表
可以用Object模拟链表

# 链表的常用操作

遍历

const a = {val: 'a'}
const b = {val: 'b'}
const c = {val: 'c'}
const d = {val: 'd'}
a.next = b 
b.next = c
c.next = d

// 遍历链表
let p = a; // p 是一个指针
while(p) { // 当 p 有值得实惠一直循环
    console.log(p.val)
    p = p.next
}

插入

// 插入
const e = {val: 'e'}

c.next = e
e.next = d

删除

c.next = d

# leetCode: 237. 删除链表中的节点

# 题目描述：

请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点。传入函数的唯一参数为要被删除的节点。

现有一个链表 -- head = [4,5,1,9]，它可以表示为:

示例 1：

输入：head = [4,5,1,9], node = 5 输出：[4,1,9] 解释：给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9. 示例 2：

输入：head = [4,5,1,9], node = 1 输出：[4,5,9] 解释：给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.

提示：

链表至少包含两个节点。链表中所有节点的值都是唯一的。给定的节点为非末尾节点并且一定是链表中的一个有效节点。不要从你的函数中返回任何结果。

# 解题思路

无法直接获取被删除节点的上个节点
被删除节点转移到下个节点

# 解题步骤

将被删节点的值改为下个节点的值
删除下个节点

const deleteNode = function(node) {
    node.val = node.next.val
    node.next = node.next.next
}

# leetCode: 206.反转链表

# 题目描述

反转一个单链表。

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

进阶: 你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

# 解题思路

反转两个节点：将 n+1 的 next 指向 n
反转多个节点：双指针遍历链表，重复上述操作

# 解题步骤

双指针一前一后遍历链表
反转双指针

const reverseList = function(head) {
    let p1 = head
    let p2 = null
    while(p1) {
        // console.log(p1.val, p2 && p2.val)
        const tmp = p1.next
        p1.next = p2
        p2 = p1 
        p1 = temp
    }
    return p2
}

# leetCode: 2. 两数相加

# 题目描述

给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例1：

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.

示例2：

输入：l1 = [0], l2 = [0]
输出：[0]

示例3：

输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]

提示：

每个链表中的节点数在范围 [1, 100] 内
0 <= Node.val <= 9
题目数据保证列表表示的数字不含前导零

# 解题思路

类似小学数学题，模拟相加操作
需要遍历链表

# 解题步骤

新建一个空链表
遍历被相加的两个链表，模拟相加操作，将个位数追加到新链表上，将十位数留到下一位去相加

← 队列二叉树 →