原文来自 我的个人博客

前言

拒绝摆烂ヾ(◍°∇°◍)ﾉﾞ

从今天开始（2023/02/12），定一个小目标，先刷个 300 道 Leetcode 题目（之前刷的不计入）。

当然作为一个小前端，我选择的语言是 TS，而且刷的题目的难度会偏中等一些，大概按照 简单3 中等6 困难1 这样的题型分布吧。嗯，目前是这么打算的。

本题 Github 地址：因为比较喜欢 vscode 的界面，而且方便调试，所以 AC 完就顺便提到 github 了，也算做一个记录吧。

本篇的题目是这个系列的第

1. NO.17：2487. 从链表中移除节点
2. NO.18：剑指 Offer II 025. 链表中的两数相加
3. NO.19：面试题 02.05. 链表求和
4. NO.20：2181. 合并零之间的节点

1. 从链表中移除节点

1.1 题目描述

给你一个链表的头节点 head 。

对于列表中的每个节点 node ，如果其右侧存在一个具有 严格更大 值的节点，则移除 node 。

返回修改后链表的头节点 head 。

示例 1：

输入： head = [5,2,13,3,8]
输出： [13,8]
解释： 需要移除的节点是 5 ，2 和 3 。
- 节点 13 在节点 5 右侧。
- 节点 13 在节点 2 右侧。
- 节点 8 在节点 3 右侧。

示例 2：

输入： head = [1,1,1,1]
输出： [1,1,1,1]
解释： 每个节点的值都是 1 ，所以没有需要移除的节点。

提示：

• 给定列表中的节点数目在范围 [1, 105] 内
• 1 <= Node.val <= 105

1.2 解法一：递归

按照正常的思维遍历链表，每次遇到右边节点比当前节点的值大的节点就删除当前节点，但是删除完之后还有判断删除的节点左边的节点与右边节点的大小，而此时我们又很难拿到左边的节点。

思路：用递归的思维，我们将链表递归到最后的节点，在递归回来的过程判读左右两个节点的大小。

function removeNodes(head: ListNode | null): ListNode | null {
  let curr: ListNode | null = head;
  if (curr && !curr.next) {
    return curr;
  }
  let newHead: ListNode | null = removeNodes(curr!.next);
  if (head!.val < newHead!.val) {
    head!.next = null;
  } else {
    head!.next = newHead
    newHead = head;
  }
  return newHead;
}

复杂度分析:

• 时间复杂度：O(n)，其中 n 为链表的长度。
• 空间复杂度：O(n)，需要 O(n) 的栈空间。

1.3 迭代：反转两次链表

这种方法的思路就是先将原先的链表反转过来，此时我们的问题从 "移除右边节点比当前节点大的当前节点" 变成了 “移除右边节点比当前节点小的右边节点”

// 1 -> 2 -> 3 -> 4 -> 5
// 1 <- 2 <- 3 <- 4 <- 5
function reverseList(head: ListNode | null): ListNode | null {
  let prev: ListNode | null = null;
  let curr: ListNode | null = head;
  let next: ListNode | null = head?.next ?? null;

  if (!curr || !next) return head;

  while (curr && next) {
    curr.next = prev;
    prev = curr;
    curr = next;
    next = next?.next;
    curr.next = prev;
  }
  return curr;
}

// 5 -> 2 -> 13 -> 3 -> 8
// 8 -> 3 -> 13 -> 2 -> 5
//13 -> 8
function removeNodes(head: ListNode | null): ListNode | null {
  let newHead = reverseList(head);
  let curr: ListNode | null = newHead;
  while (curr && curr.next) {
    while (curr && curr.next && curr.val > curr.next.val) curr.next = curr.next.next;
    curr = curr.next;
  }
  newHead = reverseList(newHead);
  return newHead;
}

复杂度分析

• 时间复杂度：O(n)，其中 n 为链表的长度。
• 空间复杂度：O(1)，仅用到若干额外变量。

2. 链表中的两数相加

2.1 题目描述

给定两个 非空链表 l1和 l2 来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。

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

示例1：

输入： l1 = [7,2,4,3], l2 = [5,6,4]
输出： [7,8,0,7]

示例2：

输入： l1 = [2,4,3], l2 = [5,6,4]
输出： [8,0,7]

示例3：

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

提示：

• 链表的长度范围为 [1, 100]
• 0 <= node.val <= 9
• 输入数据保证链表代表的数字无前导 0

进阶： 如果输入链表不能修改该如何处理？换句话说，不能对列表中的节点进行翻转。

注意：本题与主站 445 题相同：https://leetcode-cn.com/problems/add-two-numbers-ii/

2.2 解：链表反转相加

这道题的思路就是将两个链表相加，因为加法运算要从个位数开始加。加完之后再将生成的链表返回即可

function reverseList(head: ListNode | null): ListNode | null {
  let prev: ListNode | null = null;
  let curr: ListNode | null = head;
  let next: ListNode | null = curr?.next ?? null;

  while (curr && next) {
    curr.next = prev;
    prev = curr;
    curr = next;
    next = next.next;
    curr.next = prev;
  }
  return curr;
}

function addTwoNumbers(
  l1: ListNode | null,
  l2: ListNode | null
): ListNode | null {
  l1 = reverseList(l1);
  l2 = reverseList(l2);
  let tmp: number = 0;
  let ret = new ListNode();
  let p = ret;

  while (l1 && l2) {
    p.next = new ListNode((tmp + l1.val + l2.val) % 10);
    tmp = Math.floor((tmp + l1.val + l2.val) / 10);
    l1 = l1.next;
    l2 = l2.next;
    p = p.next;
  }

  while (l1) {
    p.next = new ListNode((tmp + l1.val) % 10);
    tmp = Math.floor((tmp + l1.val) / 10);
    l1 = l1.next;
    p = p.next;
  }

  while (l2) {
    p.next = new ListNode((tmp + l2.val) % 10);
    tmp = Math.floor((tmp + l2.val) / 10);
    l2 = l2.next;
    p = p.next;
  }

  if (tmp) p.next = new ListNode(tmp);
  return reverseList(ret.next);
}

3. 链表求和

3.1 题目描述

给定两个用链表表示的整数，每个节点包含一个数位。

这些数位是反向存放的，也就是个位排在链表首部。

编写函数对这两个整数求和，并用链表形式返回结果。

示例：

输入： (7 -> 1 -> 6) + (5 -> 9 -> 2)，即617 + 295
输出： 2 -> 1 -> 9，即912

进阶： 思考一下，假设这些数位是正向存放的，又该如何解决呢?

示例：

输入： (6 -> 1 -> 7) + (2 -> 9 -> 5)，即617 + 295
输出： 9 -> 1 -> 2，即912

3.2 解

这道题比上面的还要简单，都不需要反转，直接拿来加就好了

function addTwoNumbers(
  l1: ListNode | null,
  l2: ListNode | null
): ListNode | null {
  let tmp: number = 0;
  let ret: ListNode | null = new ListNode();
  let p = ret;
  while (l1 && l2) {
    p.next = new ListNode((l1.val + l2.val + tmp) % 10);
    tmp = Math.floor((l1.val + l2.val + tmp) / 10);
    l1 = l1.next;
    l2 = l2.next;
    p = p.next;
  }

  while (l1) {
    p.next = new ListNode((l1.val + tmp) % 10);
    tmp = Math.floor((l1.val + tmp) / 10);
    l1 = l1.next;
    p = p.next;
  }

  while (l2) {
    p.next = new ListNode((l2.val + tmp) % 10);
    tmp = Math.floor((l2.val + tmp) / 10);
    l2 = l2.next;
    p = p.next;
  }

  if (tmp) p.next = new ListNode(tmp);
  return ret.next;
}

4. 合并零之间的节点

4.1 题目描述

给你一个链表的头节点 head ，该链表包含由 0 分隔开的一连串整数。链表的 开端 和 末尾 的节点都满足 Node.val == 0 。

对于每两个相邻的 0 ，请你将它们之间的所有节点合并成一个节点，其值是所有已合并节点的值之和。然后将所有 0 移除，修改后的链表不应该含有任何 0 。

 返回修改后链表的头节点 head 。

**示例 1：
**

输入： head = [0,3,1,0,4,5,2,0]
输出： [4,11]
解释：
上图表示输入的链表。修改后的链表包含：
- 标记为绿色的节点之和：3 + 1 = 4
- 标记为红色的节点之和：4 + 5 + 2 = 11

**示例 2：
**

输入： head = [0,1,0,3,0,2,2,0]
输出： [1,3,4]
解释：
上图表示输入的链表。修改后的链表包含：
- 标记为绿色的节点之和：1 = 1
- 标记为红色的节点之和：3 = 3
- 标记为黄色的节点之和：2 + 2 = 4

提示：

• 列表中的节点数目在范围 [3, 2 * 105] 内
• 0 <= Node.val <= 1000
• 不 存在连续两个 Node.val == 0 的节点
• 链表的 开端 和 末尾 节点都满足 Node.val == 0

4.2 解

思路与算法：

我们设置有一个指针指向 head，边遍历链表边计算当前节点到上一个 0 节点之间节点的合 num，直到遇到下一个 0 节点，将 num 重置。

function mergeNodes(head: ListNode | null): ListNode | null {
  let curr: ListNode | null = head;
  let ret: ListNode | null = new ListNode();
  let p = ret;
  let num: number = 0;
  while(curr) {
    if(curr.val === 0 && num !== 0) {
      p.next = new ListNode(num)
      p = p.next
      num = 0
    }

    if(curr.val !== 0) {
      num += curr.val
    }
    curr = curr.next
  }
  return ret.next
}