前言

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

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

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

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

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

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 解法一：递归

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

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

ts
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 迭代：反转两次链表

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

ts
// 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 解：链表反转相加

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

ts
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 解

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

ts
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 重置。

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

目录

前言

1. 从链表中移除节点

1.1 题目描述

1.2 解法一：递归

1.3 迭代：反转两次链表

2. 链表中的两数相加

2.1 题目描述

2.2 解：链表反转相加

3. 链表求和

3.1 题目描述

3.2 解

4. 合并零之间的节点

4.1 题目描述

4.2 解