用javascript分类刷leetcode15.链表(图文视频讲解)

链表操作如下图：

动画过大，点击查看

时间复杂度：

• prepend: O(1)
• append: 如果已知尾节点O(1)，否则需要遍历到尾节点，然后加入新节点O(n)
• insert: 插入到已知节点的后面O(1)，需要先查找后插入O(n)
• lookup: O(n)
• Delete：删除已知节点O(1)，需要先查找后删除O(n)

19. 删除链表的倒数第 N 个结点 (medium)

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

示例 1：

输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]
示例 2：

输入：head = [1], n = 1
输出：[]
示例 3：

输入：head = [1,2], n = 1
输出：[1]

提示：

链表中结点的数目为 sz
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz

进阶：你能尝试使用一趟扫描实现吗？

方法1：栈

• 思路：循环链表，将所有的节点入栈，然后在弹出栈n次，就是我们需要删除的节点
• 复杂度：时间复杂度O(L)，L是链表的长度，空间复杂度O(L)。

方法2:遍历2次

• 思路：遍历一次链表的到链表的长度L，在重头遍历到L-n+1的位置就是需要删除的节点。
• 复杂度：时间复杂度O(L)，L是链表的长度，空间复杂度O(1)

方法3:遍历1次

动画过大，点击查看

• 思路：新建dummy节点指向head，指针n1，n2指向head，循环n2指针到n的位置，然后在同时移动n1，n2，直到结尾，n1，n2的距离是n，此时n1的位置就是需要删除元素的位置
• 复杂度：时间复杂度O(L)，L是链表的长度，空间复杂度O(1)

js:

var removeNthFromEnd = function (head, n) {let dummy = new ListNode();dummy.next = head;let n1 = dummy;let n2 = dummy;for (let i = 0; i <= n; i++) {//n2移动n+1次n2 = n2.next;}while (n2 !== null) {//同时移动n1，n2n1 = n1.next;n2 = n2.next;}n1.next = n1.next.next;//删除元素return dummy.next;
};

206. 反转链表（easy）

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
示例 2：

输入：head = [1,2]
输出：[2,1]
示例 3：

输入：head = []
输出：[]

提示：

链表中节点的数目范围是 [0, 5000]
-5000 <= Node.val <= 5000

方法1.头插法：

动画过大，点击查看

• 思路：准备一个临时节点，然后遍历链表，准备两个指针head和next，每次循环到一个节点的时候，将head.next指向temp.next，并且将temp.next指向head，head和next向后移一位。
• 复杂度分析：时间复杂度：O(n)， n为链表节点数，空间复杂度：O(1)

js:

var reverseList = function (head) {let temp = new ListNode();let next = null;while (head) {next = head.next;//下一个节点head.next = temp.next;temp.next = head;//head接在temp的后面head = next;//head向后移动一位}return temp.next;
};

方法2.迭代法：

动画过大，点击查看

• 思路: 遍历链表，准备prev，curr，next三个指针，在遍历的过程中，让当前指针curr.next指向前一个指针prev，然后不断让prev，curr，next向后移动，直到curr为null
• 复杂度分析：时间复杂度：O(n)， n为链表节点数，空间复杂度：O(1)

js：

var reverseList = function (head) {let prev = null;let curr = head;let next = null;while (curr !== null) {next = curr.next;//next向后移动一位curr.next = prev;//让当前指针curr.next指向前一个指针prevprev = curr;//prev向后移动一位curr = next;//curr向后移动一位//[curr.next, prev, curr] = [prev, curr, curr.next]}return prev;
};

方法3.递归：

动画过大，点击查看

• 思路：用递归函数不断传入head.next，直到head==null或者heade.next==null，到了递归最后一层的时候，让后面一个节点指向前一个节点，然后让前一个节点的next置为空，直到到达第一层，就是链表的第一个节点，每一层都返回最后一个节点。
• 复杂度分析：时间复杂度：O(n)，n是链表的长度。空间复杂度：O(n)， n是递归的深度，递归占用栈空间，可能会达到n层

js:

var reverseList = function(head) {if (head == null || head.next == null) {//递归终止条件return head;}const newHead = reverseList(head.next);//递归调用reverseListhead.next.next = head;//到了递归最后一层的时候，让后面一个节点指向前一个节点head.next = null;//前一个节点的next置为空return newHead;//返回最后一个节点
};

2. 两数相加 （medium）

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

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

你可以假设除了数字 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
题目数据保证列表表示的数字不含前导零

• 思路：循环两个链表，计算每个节点相加的和在加进位，然后计算进位，处理最后一次的进位。
• 复杂度：时间复杂度O(max(m，n))，循环的次数是链表较长的那个。空间复杂度O(1)

js：

var addTwoNumbers = function(l1, l2) {let head = null, tail = null;let carry = 0;while (l1 || l2) {//循环l1,l2链表const n1 = l1 ? l1.val : 0;const n2 = l2 ? l2.val : 0;const sum = n1 + n2 + carry;//两链表节点相加在加进位if (!head) {head = tail = new ListNode(sum % 10);//当没有节点的时候新建节点} else {tail.next = new ListNode(sum % 10);//有节点的时候则加入tail节点的后面tail = tail.next;}carry = Math.floor(sum / 10);//求进位if (l1) {//移动l1指针l1 = l1.next;}if (l2) {//移动l2指针l2 = l2.next;}}if (carry > 0) {//最后一位节点是否有进位tail.next = new ListNode(carry);}return head;
};

146. LRU 缓存机制 （medium）

请你设计并实现一个满足  LRU (最近最少使用) 缓存 约束的数据结构。
实现 LRUCache 类：
LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。
函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

示例：

输入
[“LRUCache”, “put”, “put”, “get”, “put”, “get”, “put”, “get”, “get”, “get”]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]

解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1); // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2); // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1); // 返回 -1 (未找到)
lRUCache.get(3); // 返回 3
lRUCache.get(4); // 返回 4

提示：

1 <= capacity <= 3000
0 <= key <= 10000
0 <= value <= 105
最多调用 2 * 105 次 get 和 put

• 思路：准备一个哈希表和双向链表存储键值对，哈希表O(1)就能查找到键值对，双向链表方便从链表头部新增节点，也可以从队尾删除节点

  1. get的时候，查找哈希表中有没有该键值对，不存在就返回-1，存在就返回该节点的值，并且将该节点移动到链表的头部
  2. put的时候，查找哈希表中有没有该键值对，如果存在就更新该节点，并且移动到链表的头部，不存在就创建一个节点，加入到哈希表和链表的头部，并且让节点数count+1，如果超出容量，就从队尾删除一个节点

• 复杂度：put、get时间复杂度都是O(1)，空间复杂度O(c)，c是LRU的容量

js:

class ListNode {constructor(key, value) {//双向链表的单个节点this.key = keythis.value = valuethis.next = null //指向后一个节点this.prev = null //指向前一个节点}
}class LRUCache {constructor(capacity) {this.capacity = capacity //容量this.hashTable = {} //存放键值对信息this.count = 0 //键值对数量this.dummyHead = new ListNode() //dummy头节点 方便在链表从开始的地方插入this.dummyTail = new ListNode()    //dummy尾节点 方便在链表从末尾删除this.dummyHead.next = this.dummyTail //dummyHead和dummyTail相互连接this.dummyTail.prev = this.dummyHead}get(key) {let node = this.hashTable[key]//查找哈希表中的键值对if (node == null) return -1 //不存在该键值对 返回-1this.moveToHead(node) //移动到链表头return node.value}put(key, value) {let node = this.hashTable[key] //哈希表中查找该键值对if (node == null) {let newNode = new ListNode(key, value) //不存在就创建节点this.hashTable[key] = newNode //加入哈希表this.addToHead(newNode) //加入链表头this.count++ //节点数+1if (this.count > this.capacity) { //超过容量 从队尾删除一个this.removeLRUItem()}} else {node.value = value //键值对存在于哈希表中 就更新this.moveToHead(node) //移动到队头}}moveToHead(node) {this.removeFromList(node)//从链表中删除节点this.addToHead(node)//将该节点添加到链表头}removeFromList(node) {//删除的指针操作let tempForPrev = node.prevlet tempForNext = node.nexttempForPrev.next = tempForNexttempForNext.prev = tempForPrev}addToHead(node) {//加入链表头的指针操作node.prev = this.dummyHeadnode.next = this.dummyHead.nextthis.dummyHead.next.prev = nodethis.dummyHead.next = node}removeLRUItem() {let tail = this.popTail()//从链表中删除delete this.hashTable[tail.key]//从哈希表中删除this.count--}popTail() {let tailItem = this.dummyTail.prev//通过dummyTail拿到最后一个节点 然后删除this.removeFromList(tailItem)return tailItem}
}

328. 奇偶链表 (medium)

给定单链表的头节点 head ，将所有索引为奇数的节点和索引为偶数的节点分别组合在一起，然后返回重新排序的列表。

第一个节点的索引被认为是 奇数 ， 第二个节点的索引为 偶数 ，以此类推。

请注意，偶数组和奇数组内部的相对顺序应该与输入时保持一致。

你必须在 O(1) 的额外空间复杂度和 O(n) 的时间复杂度下解决这个问题。

示例 1:

输入: head = [1,2,3,4,5]
输出: [1,3,5,2,4]
示例 2:

输入: head = [2,1,3,5,6,4,7]
输出: [2,3,6,7,1,5,4]

提示:

n ==  链表中的节点数
0 <= n <= 104
-106 <= Node.val <= 106

动画过大，点击查看

• 思路：奇偶指针循环链表，奇数指针不断串连奇数节点，偶数指针不断串连偶数节点，最后奇数指针的结尾连接偶数节点的开始
• 复杂度：时间复杂度O(n)，空间复杂度O(1)

js：

var oddEvenList = function(head) {if (head === null) {return head;}let evenHead = head.next;let odd = head, even = evenHead;while (even !== null && even.next !== null) {//偶数指针不为空 继续循环odd.next = even.next;//奇数指针指向偶数指针的nextodd = odd.next;//移动奇数指针even.next = odd.next;//偶数指针指向奇数指针的nexteven = even.next;//移动偶数指针}odd.next = evenHead;//奇数指针结尾连接上偶数指针的开始return head;
};

203. 移除链表元素 (easy)

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

示例 1：

输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]
示例 2：

输入：head = [], val = 1
输出：[]
示例 3：

输入：head = [7,7,7,7], val = 7
输出：[]

提示：

列表中的节点数目在范围 [0, 104] 内
1 <= Node.val <= 50
0 <= val <= 50

方法1.递归

• 思路：递归调用函数removeElements，传入head.next和 val，如果当前元素值是val，则返回下一个元素，否则直接返回当前元素
• 复杂度：时间复杂度O(n)，n是链表的长度，空间复杂度是O(n)，递归栈的深度，最大为n

js：

//例：0->1->2->3  val=2
//level1: 0.next = removeElements(1, 2);            return 1                    0->1->3->null
//level2: 1.next = removeElements(2, 2);            return 3                    1->3->null
//level3: 2.next = removeElements(3, 2);            return 3                    2->3->null
//level4: 3.next = removeElements(null, 2);     return null;        3->nullvar removeElements = function(head, val) {if (head === null) {//递归终止 遍历完了链表return head;}head.next = removeElements(head.next, val);//递归调用函数removeElementsreturn head.val === val ? head.next : head;//如果当前元素值是val，则返回下一个元素，否则直接返回当前元素
};

方法2.迭代

• 思路：创建dummy节点，将dummy节点的next指向head，temp指向dummy，当temp的next不为null 不断移动temp指针，当temp的next值是要删除的 则删除该节点
• 复杂度：时间复杂度O(n)，n是链表的长度，空间复杂度是O(1)

js：

//2->1->2->3
//dummy->2->1->2->3
var removeElements = function(head, val) {const dummyHead = new ListNode(0);//创建dummy节点，将dummy节点的next指向head，temp指向dummydummyHead.next = head;let temp = dummyHead;while (temp.next !== null) {//当temp的next不为null 不断循环节点if (temp.next.val == val) {temp.next = temp.next.next;//当temp的next值是要删除的 则删除该节点} else {temp = temp.next;//移动temp指针}}return dummyHead.next;
};

237. 删除链表中的节点（easy）

有一个单链表的 head，我们想删除它其中的一个节点 node。

给你一个需要删除的节点 node 。你将 无法访问 第一个节点  head。

链表的所有值都是 唯一的，并且保证给定的节点 node 不是链表中的最后一个节点。

删除给定的节点。注意，删除节点并不是指从内存中删除它。这里的意思是：

给定节点的值不应该存在于链表中。
链表中的节点数应该减少 1。
node 前面的所有值顺序相同。
node 后面的所有值顺序相同。
自定义测试：

对于输入，你应该提供整个链表 head 和要给出的节点 node。node 不应该是链表的最后一个节点，而应该是链表中的一个实际节点。
我们将构建链表，并将节点传递给你的函数。
输出将是调用你函数后的整个链表。

示例 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

提示：

链表中节点的数目范围是 [2, 1000]
-1000 <= Node.val <= 1000
链表中每个节点的值都是 唯一 的
需要删除的节点 node 是 链表中的节点 ，且 不是末尾节点

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-EYqQCezi-1676869185119)(null)]

• 思路：将要删除节点的下一个节点的值覆盖自己的值，然后让当前节点指向下一个节点的next
• 复杂度：时间复杂度和空间复杂度都是O(1)

js：

var deleteNode = function(node) {node.val = node.next.val//将要删除节点的下一个节点的值覆盖自己的值Ïnode.next = node.next.next//让当前节点指向下一个节点的next
};

24. 两两交换链表中的节点 （medium）

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

示例 1：

输入：head = [1,2,3,4]
输出：[2,1,4,3]
示例 2：

输入：head = []
输出：[]
示例 3：

输入：head = [1]
输出：[1]

提示：

链表中节点的数目在范围 [0, 100] 内
0 <= Node.val <= 100

方法1.递归：

• 思路：用递归函数不断传入链表的下一个节点，终止条件是head === null|| head.next === null，也就是至少存在两个节点进行两两交换，在最后一层的时候开始两两反转，让当前递归层的head.next指向交换后返回的头节点，然后让反转后的新的头节点指向当前层的head的节点，这样就实现了两两交换，最后返回反转后链表的头节点
• 复杂的分析：时间复杂度O(n)， n 是链表的节点数量。空间复杂度O(n)，n是递归调用的栈空间

js:

var swapPairs = function(head) {if (head === null|| head.next === null) {//终止条件，必须要有两个节点return head;}const newHead = head.next;//反转后链表的头节点，head.next = swapPairs(newHead.next);//让当前递归层的head.next指向交换后返回的头节点newHead.next = head;//让反转后的新的头节点指向当前层的head的节点return newHead;//返回反转后的头节点
};

方法2.循环(虚拟头节点)

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-r173iraz-1676869182813)(null)]

• 思路：设置虚拟头节点dummyHead，让dummyHead.next指向head,当temp.next !== null && temp.next.next !== null的时候，也就是dummyHead后面存在至少两个节点，才开始两两交换节点。交换之前准备三个指针temp指向dummyHead，node1是dummyHead后面的第一个节点，node2是dummyHead后的第二个节点，交换的时候让temp.next指向node2，node1.next指向node2.next，node2.next指向node1，每次循环迭代让这三个节点后移一个节点，最后返回dummyHead.next，核心步骤是

  temp.next = node2;
  node1.next = node2.next;
  node2.next = node1;
  

• 复杂的分析：时间复杂度O(n)， n 是链表的节点数量。空间复杂度O(1)，

Js:

var swapPairs = function(head) {const dummyHead = new ListNode(0);//虚拟头节点dummyHead.next = head;//初始的时候让虚拟头节点指向head，let temp = dummyHead;//temp指针while (temp.next !== null && temp.next.next !== null) {//循环条件，dummyHead后存在至少两个节点const node1 = temp.next;//node1指针，即dummyHead后的第一个节点const node2 = temp.next.next;//node2指针，即dummyHead后的第二个节点temp.next = node2;//下面三行是两两交换的核心代码node1.next = node2.next;node2.next = node1;temp = node1;//后移一个节点的位置}return dummyHead.next;//返回交换后的头节点
};

21. 合并两个有序链表 (easy)

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例 1：

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
示例 2：

输入：l1 = [], l2 = []
输出：[]
示例 3：

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

提示：

两个链表的节点数目范围是 [0, 50]
-100 <= Node.val <= 100
l1 和 l2 均按 非递减顺序 排列

方法1.递归

• 思路：递归合并节点，当前节点谁小，就让这个较小的节点的next和另一个链表继续递归合并，直到两个链表有一个的nxet不存在了，那就没法分割问题了，只能返回
• 复杂度：时间复杂度O(m+n)，m、n为两个链表的长度，每次递归排除掉一个节点，总递归次数是m+n。空间复杂度O(m+n)，递归栈空间

js：

var mergeTwoLists = function(l1, l2) {//递归终止 分隔到不能分割 也就是两个链表有一个的nxet不存在了 那就没法分割问题了 只能返回if (l1 === null) {return l2;} else if (l2 === null) {return l1;} else if (l1.val < l2.val) {//当前节点谁小，就让这个较小的节点的next和另一个链表继续递归合并l1.next = mergeTwoLists(l1.next, l2);//分隔成合并l1.next, l2的子问题return l1;} else {l2.next = mergeTwoLists(l1, l2.next);return l2;}
};

方法2.迭代

动画过大，点击查看

• 思路：设立虚拟头节点prehead，prev节点初始指向prehead，循环两个链表，两个链表中小的节点接在prev的后面，不断移动prev，最后返回prehead.next
• 复杂度：时间复杂度O(m+n)，m、n为两个链表的长度，循环m+n次。空间复杂度O(1)

js：

var mergeTwoLists = function(l1, l2) {const prehead = new ListNode(-1);//虚拟头节点let prev = prehead;while (l1 != null && l2 != null) {//循环两个链表if (l1.val <= l2.val) {//小的节点接在prev的后面prev.next = l1;l1 = l1.next;//向后移动l1} else {prev.next = l2;//向后移动l2l2 = l2.next;}prev = prev.next;向后移动prev}prev.next = l1 === null ? l2 : l1;//两个链表一个遍历完，另一个可能还没遍历完，没遍历完的接上return prehead.next;//返回prehead.next
};

92. 反转链表 II(medium)

给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。

示例 1：

输入：head = [1,2,3,4,5], left = 2, right = 4
输出：[1,4,3,2,5]
示例 2：

输入：head = [5], left = 1, right = 1
输出：[5]

提示：

链表中节点数目为 n
1 <= n <= 500
-500 <= Node.val <= 500
1 <= left <= right <= n

方法1

动画过大，点击查看

• 思路：切断left到right的子链，然后反转，最后在反向连接
• 复杂度：时间复杂度O(n)，空间复杂度O(1)

js：

var reverseBetween = function(head, left, right) {const dummyNode = new ListNode(-1);dummyNode.next = head;//虚拟头节点let pre = dummyNode;for (let i = 0; i < left - 1; i++) {//pre遍历到left的前一个节点pre = pre.next;}let rightNode = pre;for (let i = 0; i < right - left + 1; i++) {//rightNode遍历到right的位置rightNode = rightNode.next;}let leftNode = pre.next;//保存leftNodelet curr = rightNode.next;//保存rightNode.next//切断left到right的子链pre.next = null;rightNode.next = null;//206题的逻辑 反转left到right的子链reverseLinkedList(leftNode);//返乡连接pre.next = rightNode;leftNode.next = curr;return dummyNode.next;
};const reverseLinkedList = (head) => {let pre = null;let cur = head;while (cur) {const next = cur.next;cur.next = pre;pre = cur;cur = next;}
}

方法2

动画过大，点击查看

• 思路：从left遍历到right，在遍历的过程中反转链表
• 复杂度：时间复杂度O(n)，空间复杂度O(1)

js：

var reverseBetween = function(head, left, right) {const dummy_node = new ListNode(-1);dummy_node.next = head;//虚拟头节点let pre = dummy_node;for (let i = 0; i < left - 1; ++i) {//pre前进到left的前一个节点pre = pre.next;}let cur = pre.next;for (let i = 0; i < right - left; ++i) {//循环right - left次 反转中间的节点const next = cur.next;cur.next = next.next;next.next = pre.next;pre.next = next;}return dummy_node.next;//返回虚拟头节点的next
};

视频讲解：传送门