代码随想录刷题记录-Day03

发表于 更新于 本文字数： 3k 阅读时长 ≈ 11 分钟

To Do List

  • DAY 3 回顾
  • 对链表结构的理解
  • LeetCode 203. 移除链表元素 / Remove Linked List Elements
  • 203 题相似题目
  • …
  • 再提循环不变量：LeetCode 59. 螺旋矩阵 II / Spiral Matrix II
  • 59 题扩展题目
  • 总结 / Summary

1. DAY 1 回顾

Day 1 学习内容：Link

  • 认识了数组的基本结构和增删查改操作。
  • 学习了二分法以及双指针法
  • 一刷 LeetCode 6 题 Link

2. 对链表结构的理解

链表同样也是一个非常重要的数据结构。

链表是一个通过指针 (pointer) 来串联在一起的一种线性结构。（如图）

链表当中的每一个节点均有两部分组成：一个是数据域，用来存放每个节点的数据；另一个是指针域，专门用来存放指向下一个节点的指针。

链表的第一个节点称为头节点（也叫入口节点） 卡哥对链表头节点的定义的理解可能有些误差，其实链表的第一个（存储数据的）节点叫做首节点（也叫首元节点），指向首节点的节点才叫做头节点（链表可以没有这个头节点，增设这个节点可以降低求解的难度），可以不存储数据信息的实打实的头节点！ 指向首节点的指针叫做头指针！最后一个节点称为尾节点，其指针指向的是空指针（简称空或 null）

链表的类型

1
2
3
单链表：单链表的指针只能指向上一个节点。只能向后单向查询。
双链表：双链表与单链表相比多了一个指针域，用来指向上一个节点，需注意首节点的上一个节点为空指针（简称空或 null）。可以向前或向后查询。
循环链表：链表的首尾相连。

链表存储方式

数组在内存中连续分布，而链表是通过指针来指向内存中的各个节点。节点的内存位置也不是固定的，分到什么样的地址均由操作系统的内存分配机制来决定。

3. LeetCode 203. 移除链表元素 / Remove Linked List Elements

1
Difficulty: Easy

Given the head of a linked list and an integer val, remove all the nodes of the linked list that has Node.val == val, and return the new head.

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

Example 1:

removelinklist

1
2
Input: head = [1,2,6,3,4,5,6], val = 6
Output: [1,2,3,4,5]

Example 2:

1
2
Input: head = [], val = 1
Output: []

Example 3:

1
2
Input: head = [7,7,7,7], val = 7
Output: []

Constraints:

  • The number of nodes in the list is in the range [0, 104].
  • 1 <= Node.val <= 50
  • 0 <= val <= 50
Translated by zh-CN 列表中的节点数目在范围 [0, 104] 内； 1 <= Node.val <= 50； 0 <= val <= 50.

解法：

JavaScript

(1) 在元链表上删除

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * 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} val
 * @return {ListNode}
 */
var removeElements = function (head, val) {
    let first = head

    while (first != null && first.val == val) {
        first = first.next
    }
    let current = first
    while (current != null && current.next != null) {
        if (current.next.val == val) {
            current.next = current.next.next
        } else current = current.next
    }
    return first
};

(2) 添加虚拟头节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
 * 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} val
 * @return {ListNode}
 */
var removeElements = function (head, val) {
    
    let first = head
    let fakehead = new ListNode(0, first)
    fakehead.next = first
    let current = fakehead
    while(current.next != null) {
        if (current.next.val == val){
            current.next = current.next.next
        } else current = current.next
    }
    return fakehead.next
};

(Under Construction)

4. 203 题类似题目

LeetCode 237. 删除链表中的节点 / Delete Node in a Linked List

1
Difficulty: Medium

There is a singly-linked list head and we want to delete a node node in it.

You are given the node to be deleted node. You will not be given access to the first node of head.

All the values of the linked list are unique, and it is guaranteed that the given node node is not the last node in the linked list.

Delete the given node. Note that by deleting the node, we do not mean removing it from memory. We mean:

  • The value of the given node should not exist in the linked list.
  • The number of nodes in the linked list should decrease by one.
  • All the values before node should be in the same order.
  • All the values after node should be in the same order.

Custom testing:

  • For the input, you should provide the entire linked list head and the node to be given node. node should not be the last node of the list and should be an actual node in the list.
  • We will build the linked list and pass the node to your function.
  • The output will be the entire list after calling your function.
Translated by zh-CN 有一个单链表的 head，我们想删除它其中的一个节点 node。
给你一个需要删除的节点 node 。你将 无法访问 第一个节点 head。
链表的所有值都是 唯一的，并且保证给定的节点 node 不是链表中的最后一个节点。
删除给定的节点。注意，删除节点并不是指从内存中删除它。这里的意思是：
1. 给定节点的值不应该存在于链表中。
2. 链表中的节点数应该减少 1。
3. node 前面的所有值顺序相同。
4. node 后面的所有值顺序相同。
自定义测试：
对于输入，你应该提供整个链表 head 和要给出的节点 node。node 不应该是链表的最后一个节点，而应该是链表中的一个实际节点。我们将构建链表，并将节点传递给你的函数。输出将是调用你函数后的整个链表。

Example 1:

237_example1

1
2
3
Input: head = [4,5,1,9], node = 5
Output: [4,1,9]
Explanation: You are given the second node with value 5, the linked list should become 4 -> 1 -> 9 after calling your function.(指定链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9)

Example 2:

237_example2

1
2
3
Input: head = [4,5,1,9], node = 1
Output: [4,5,9]
Explanation: You are given the third node with value 1, the linked list should become 4 -> 5 -> 9 after calling your function.(指定链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9)

Constraints:

  • The number of the nodes in the given list is in the range [2, 1000].
  • -1000 <= Node.val <= 1000
  • The value of each node in the list is unique.
  • The node to be deleted is in the list and is not a tail node.
Translated by zh-CN 1. 链表中节点的数目范围是 [2, 1000]
2. -1000 <= Node.val <= 1000
3. 链表中每个节点的值都是 唯一 的
4. 需要删除的节点 node 是 链表中的节点 ，且 不是末尾节点

解法：

JavaScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} node
 * @return {void} Do not return anything, modify node in-place instead.
 */
var deleteNode = function(node) {
    node.val = node.next.val
    node.next = node.next.next
};

PS: 说实话这道题出的并不是很好，这道题的题目描述不论是中文还是英文要看懂很有难度，也不知道中英文出题者到底在想什么，满题的删除删除删除，咋不把你的脑子删除了呢（X）回到正题，一般删除链表中节点，需要用到头节点和临时指针等来进行删除链表元素的操作的。而这一题传入的参数只有 node (链表当中的其中一个节点)，这就说明之前提到的两种解法是不管用的，由于这题的用例都是单链表，所以只有一个方法，就是用下一个节点来覆盖即可。反正我的评价是，这道题的正统在第 203 题，这道题的正统在第 203 题，这道题的正统在第 203 题

5. 链表的操作（增删）

1
没有改查

5.1 删除操作

假设当前节点的指针是 current, 要删除的节点指针为 current.next, 那么只需将当前节点的下一个指针直接指向下下一个指针，也就是

1
2
3
4
5
Before: current -> current.next

current.next = current.next.next

After: current -> current.next.next

C / C++ 涉及到的内存回收机制此处不再介绍。

可以看到删除节点只需修改相应的指针指向即可，不用进行查询操作，故时间复杂度为O(1).

5.2 添加节点操作

假设当前节点的指针是 current, 要添加的节点指针为 new，只需将当前节点的下一个节点指向新节点，也就是

1
2
3
4
5
6
Before: current -> current.next

current.next = new
new.next = current.next

After: current -> new -> current.next

可以看到添加节点也只需修改相应的指针指向即可，不用进行查询操作，故时间复杂度为O(1).

此处也有个特例，就是如果在新链表里删除尾节点，需要再进行一次查询到倒数第二个节点，让其指针指向空指针完成删除操作。此时间复杂度为O(n).

5.3 性能对比

如下表所示。

增删 查 特点
数组 O(n) O(1) 查询速度快
链表 O(1) O(n) 增删操作速度快

6. LeetCode 707. 设计链表 / Design Linked List

1
Difficulty: Medium

Design your implementation of the linked list. You can choose to use a singly or doubly linked list.
A node in a singly linked list should have two attributes: val and next. val is the value of the current node, and next is a pointer/reference to the next node.
If you want to use the doubly linked list, you will need one more attribute prev to indicate the previous node in the linked list. Assume all nodes in the linked list are 0-indexed.

Implement the MyLinkedList class:

  • MyLinkedList() Initializes the MyLinkedList object.
  • int get(int index) Get the value of the indexth node in the linked list. If the index is invalid, return -1.
  • void addAtHead(int val) Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list.
  • void addAtTail(int val) Append a node of value val as the last element of the linked list.
  • void addAtIndex(int index, int val) Add a node of value val before the indexth node in the linked list. If index equals the length of the linked list, the node will be appended to the end of the linked list. If index is greater than the length, the node will not be inserted.
  • void deleteAtIndex(int index) Delete the indexth node in the linked list, if the index is valid.
Translated by zh-CN 你可以选择使用单链表或者双链表，设计并实现自己的链表。
单链表中的节点应该具备两个属性：val 和 next 。val 是当前节点的值，next 是指向下一个节点的指针/引用。
如果是双向链表，则还需要属性 prev 以指示链表中的上一个节点。假设链表中的所有节点下标从 0 开始。

实现 MyLinkedList 类：
MyLinkedList() 初始化 MyLinkedList 对象。
int get(int index) 获取链表中下标为 index 的节点的值。如果下标无效，则返回 -1 。
void addAtHead(int val) 将一个值为 val 的节点插入到链表中第一个元素之前。在插入完成后，新节点会成为链表的第一个节点。
void addAtTail(int val) 将一个值为 val 的节点追加到链表中作为链表的最后一个元素。
void addAtIndex(int index, int val) 将一个值为 val 的节点插入到链表中下标为 index 的节点之前。如果 index 等于链表的长度，那么该节点会被追加到链表的末尾。如果 index 比长度更大，该节点将 不会插入 到链表中。
void deleteAtIndex(int index) 如果下标有效，则删除链表中下标为 index 的节点。

Example 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Input
["MyLinkedList", "addAtHead", "addAtTail", "addAtIndex", "get", "deleteAtIndex", "get"]
[[], [1], [3], [1, 2], [1], [1], [1]]
Output
[null, null, null, null, 2, null, 3]

解释
MyLinkedList myLinkedList = new MyLinkedList();
myLinkedList.addAtHead(1);
myLinkedList.addAtTail(3);
myLinkedList.addAtIndex(1, 2);    // 链表变为 1->2->3
myLinkedList.get(1);              // 返回 2
myLinkedList.deleteAtIndex(1);    // 现在，链表变为 1->3
myLinkedList.get(1);              // 返回 3

Constraints:

  • 0 <= index, val <= 1000
  • Please do not use the built-in LinkedList library.
  • At most 2000 calls will be made to get, addAtHead, addAtTail, addAtIndex and deleteAtIndex.
Translated by zh-CN 0 <= index, val <= 1000.
请不要使用内置的 LinkedList 库。
调用 get、addAtHead、addAtTail、addAtIndex 和 deleteAtIndex 的次数不超过 2000 。

解法：

JavaScript

7. 链表与双指针法的经典结合：LeetCode 206. 翻转链表 / Reverse Linked List

1
Difficulty: Easy

Given the head of a singly linked list, reverse the list, and return the reversed list.

Example 1:

1
2
Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]

Example 2:

1
2
Input: head = [1,2]
Output: [2,1]

Example 3:

1
2
Input: head = []
Output: []

Constraints:

  • The number of nodes in the list is the range [0, 5000].
  • -5000 <= Node.val <= 5000

Follow up: A linked list can be reversed either iteratively or recursively. Could you implement both?

解法：

JavaScript