系列目錄

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時稱為空表

性質

1. 集合中必存在唯一的一個“第一元素”：線性表有明確的起始點
2. 集合中必存在唯一的一個“最后元素”：線性表有明確的終止點
3. 除最后一個元素之外，均有唯一的后繼( 后件)：除了最后一個元素，每個元素后面都跟著一個元素
4. 除第一個元素之外，均有唯一的前驅( 前件)：除了第一個元素，每個元素前面都有一個元素
5. 線性表能夠逐項訪問和順序存取：可以按照元素的順序進行訪問和存儲

分類

• 一般線性表：可以自由地進行刪除或添加操作
• 受限線性表：主要包括棧( 后進先出)和隊列( 先進先出)，對結點的操作有限制

基本操作

1. MakeEmpty(L)：將L變為空表
2. Length(L)：返回表L的長度，即表中元素個數
3. Get(L, i)：返回L中位置i處的元素( 1≤i≤n)
4. Prior(L, i)：取i的前驅元素
5. Next(L, i)：取i的后繼元素
6. Locate(L, x)：返回元素x在L中的位置
7. Insert(L, i, x)：在表L的位置i處插入元素x，將原占據位置i的元素及后面的元素都向后推一個位置
8. Delete(L, p)：從表L中刪除位置p處的元素
9. 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 仍然是一個很好的選擇，特別是當對象的構造過程涉及多個參數或復雜邏輯時