LeetCode经典题之876、143 题解及延伸

系列目录

88.合并两个有序数组
52.螺旋数组
567.字符串的排列
643.子数组最大平均数
150.逆波兰表达式
61.旋转链表
160.相交链表
83.删除排序链表中的重复元素
389.找不同
1491.去掉最低工资和最高工资后的工资平均值
896.单调序列
206.反转链表
92.反转链表II
141.环形链表
142.环型链表

876. 链表的中间节点

🌟线性表/动态数组+快慢指针

原题链接

C++
若未特殊标明，以下题解均写用C++

方法一 快慢指针

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* middleNode(ListNode* head) {ListNode *slow = head, *fast = head;// 记得一定要先对fast 进行检查while (fast != nullptr && fast->next != nullptr) {slow = slow->next;fast = fast->next->next;}return slow;}
};

先检查 fast 是为了确保在尝试访问 fast->next 之前，fast 不是 nullptr，从而可以避免未定义行为

方法二 线性表/动态数组

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* middleNode(ListNode* head) {// 定义一个类似于数组特性的线性表——支持下标访问vector<ListNode*> a = {head};// a.back()取原线性表的最后一个元素while (a.back()->next != nullptr)a.push_back(a.back()->next);// C++ 默认向下取整return a[a.size() / 2];}
};

注解：

vector<ListNode*> a = {head};

vector的元素为链表的节点ListNode*——这也是我们为什么要nullptr的原因

并创建一个包含单个元素( 即head指针)的vector

若没有{head}，则定义的是一个空的容器vector

线性表

定义

线性表( Linear List)是数据结构的一种，它是一个具有相同特性的数据元素的有限序列
数据元素之间的关系是一对一的，即除了第一个和最后一个数据元素之外，其他数据元素都是首尾相接的
线性表的个数n定义为线性表的长度，n=0时称为空表

性质

集合中必存在唯一的一个“第一元素”：线性表有明确的起始点
集合中必存在唯一的一个“最后元素”：线性表有明确的终止点
除最后一个元素之外，均有唯一的后继( 后件)：除了最后一个元素，每个元素后面都跟着一个元素
除第一个元素之外，均有唯一的前驱( 前件)：除了第一个元素，每个元素前面都有一个元素
线性表能够逐项访问和顺序存取：可以按照元素的顺序进行访问和存储

分类

一般线性表：可以自由地进行删除或添加操作
受限线性表：主要包括栈( 后进先出)和队列( 先进先出)，对结点的操作有限制

基本操作

MakeEmpty(L)：将L变为空表
Length(L)：返回表L的长度，即表中元素个数
Get(L, i)：返回L中位置i处的元素( 1≤i≤n)
Prior(L, i)：取i的前驱元素
Next(L, i)：取i的后继元素
Locate(L, x)：返回元素x在L中的位置
Insert(L, i, x)：在表L的位置i处插入元素x，将原占据位置i的元素及后面的元素都向后推一个位置
Delete(L, p)：从表L中删除位置p处的元素
IsEmpty(L)：判断L是否为空表

应用场景

通讯录管理：每个联系人作为线性表的一个元素，包含姓名、电话号码、地址等属性
缓存替换算法：如最近最少使用算法(LRU)和先进先出算法(FIFO)，使用线性表结构便于对缓存中的数据进行插入、删除和查找操作
任务调度系统：将需要执行的任务按照一定的优先级顺序存储在线性表中
计算机图形学：顶点表用于存储图形模型的顶点信息，每个元素表示一个顶点
公交线路查询系统：线路信息可以用线性表来存储，每个线路作为线性表的一个元素

优点

逻辑结构简单，便于实现和操作
广泛应用于各种实际场景中，是数据处理和存储的基础结构之一

143. 重排链表

🌟线性表/动态数组

原题链接

C++
若未特殊标明，以下题解均写用C++

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:void reorderList(ListNode* head) {// 特况if (head == nullptr) return;// 定义一个空线性表 Linear Listvector<ListNode*> LL;ListNode* node = head;// 将 链表节点 存入 线性表中while (node != nullptr) {LL.emplace_back(node);node = node->next;}// 下标从0开始int i = 0, j = LL.size() - 1;while (i < j) {// 像数组一样 可用下标访问LL[i]->next = LL[j];i ++;// 如LL.size() = 2，提前结束循环if (i == j)break;LL[j]->next = LL[i];// 用完 j 再更新j --;}// 最后别忘了 指向空LL[i]->next = nullptr;}
};

push_back()与emplace_back()

push_back()

push_back 是 std::vector 的一个成员函数，用于在容器的末尾添加一个元素当你使用 push_back 时，你需要提供一个与容器内元素类型相同的对象( 或者一个可以隐式转换为该类型的对象) 这个对象会被复制( 如果类型支持复制)或移动( 如果类型支持移动并且提供了右值引用)到容器的末尾

示例：

#include <vector>  
#include <string>  int main() {  std::vector<std::string> vec;  // 使用 push_back 添加一个字符串  std::string str = "Hello";  vec.push_back(str); // 这里可能发生复制或移动操作  // 也可以直接使用临时对象  vec.push_back(std::string("World")); // 这里一定会发生复制操作( 因为我们是用一个右值来初始化一个临时对象)  return 0;  
}

在上面的例子中，当你使用 push_back 并传递一个 std::string 对象时，如果 str 是一个左值( 即具有持久身份的对象)，那么它可能会被复制或移动( 取决于 std::string 的实现和编译器优化) 如果你传递一个右值( 如临时对象)，那么通常会发生复制操作，因为右值通常不被视为可移动的对象( 尽管在某些情况下，编译器可能会进行优化以消除不必要的复制)

emplace_back()

emplace_back 是 C++11 引入的一个成员函数，旨在提供比 push_back 更高的性能与 push_back 不同，emplace_back 允许你直接在容器的末尾构造一个元素，而不是先创建一个对象然后将其复制或移动到容器中这通常可以避免不必要的复制或移动操作，尤其是在处理大型或复杂的对象时

emplace_back 接受与要构造的对象构造函数相同的参数，并在容器的末尾直接调用该构造函数

示例：

#include <vector>  
#include <string>  int main() {  std::vector<std::string> vec;  // 使用 emplace_back 直接在容器末尾构造一个字符串  vec.emplace_back("Hello"); // 直接在vec的末尾构造一个std::string对象，没有复制或移动  // 也可以传递多个参数给构造函数  vec.emplace_back(5, 'a'); // 构造一个包含5个'a'字符的std::string对象  return 0;  
}

在上面的例子中，emplace_back 直接在 vec 的末尾构造了一个 std::string 对象，没有涉及任何复制或移动操作
这通常比使用 push_back 并传递一个临时对象更高效

总结：

push_back 和 emplace_back 都用于在 std::vector 的末尾添加元素，但 emplace_back 通过直接在容器中构造元素来避免不必要的复制或移动操作，从而可能提供更高的性能

虽然 emplace_back 通常比 push_back 更高效，但在某些情况下(特别是当元素类型支持移动语义且移动操作比复制操作更快时)，push_back 可能会使用移动操作来优化性能
然而，emplace_back 仍然是一个很好的选择，特别是当对象的构造过程涉及多个参数或复杂逻辑时