一、增刪查改

1.1增（插入節點）

序號	題目	鏈接
1	兩數后插入公約數	https://leetcode.cn/problems/insert-greatest-common-divisors-in-linked-list/description/?envType=problem-list-v2&envId=linked-list
2	循環有序鏈表的插入	https://leetcode.cn/problems/4ueAj6/description/?envType=problem-list-v2&envId=linked-list

1.1.1兩數后插入公約數

在兩個數A和B的中間插入A和B的公約數【公約數的值可以用gcd直接求】

//求最大公約數gcd
ListNode* insertGreatestCommonDivisors(ListNode* head) {if(head==nullptr || head->next==nullptr)return head;ListNode* p=head;while(p->next!=nullptr){ListNode* node=new ListNode(gcd(p->val,p->next->val));node->next=p->next;p->next=node;p=p->next->next;}return head;
}

1.1.2循環有序鏈表的插入

給定循環單調非遞減列表中的一個點，寫一個函數向這個列表中插入一個新元素 insertVal ，使這個列表仍然是循環升序的。

Node* insert(Node* head, int insertVal) {Node* node=new Node(insertVal);//創建新節點if(head==nullptr){node->next=node;return node;}if(head->next==head){head->next=node;node->next=head;return head;}Node* cur=head;Node* next=head->next;while(next != head){if(cur->val <= insertVal && insertVal <= next->val) break;if((cur->val > next->val) && (insertVal >= cur->val || insertVal <= next->val) )  break;cur=cur->next;next=next->next;}node->next=next;cur->next=node;return head;
}

1.2刪（移除節點）

序號	題目	鏈接
1	刪除鏈表中值為val的節點（簡單）	https://leetcode.cn/problems/remove-linked-list-elements/description/?envType=problem-list-v2&envId=linked-list
2	刪除已知的node節點	https://leetcode.cn/problems/delete-node-in-a-linked-list/description/?envType=problem-list-v2&envId=linked-list
3	移除鏈表中數組已存在的元素	https://leetcode.cn/problems/delete-nodes-from-linked-list-present-in-array/?envType=problem-list-v2&envId=linked-list
4	刪除和為0的連續節點	https://leetcode.cn/problems/remove-zero-sum-consecutive-nodes-from-linked-list/description/?envType=problem-list-v2&envId=linked-list

1.2.1刪除已知的node節點【交換val值】

void deleteNode(ListNode* node) {//將node和后面的節點換個位置，然后刪除int val=node->val;//暫存節點信息node->val=node->next->val;node->next->val=val;//刪除node->next即可node->next=node->next->next;
}

1.2.2移除數組中已存在的節點【unordered_set】

ListNode* modifiedList(vector<int>& nums, ListNode* head) {ListNode* dummy=new ListNode(-1,head);unordered_set<int> s(nums.begin(),nums.end());ListNode* pre=dummy;ListNode* cur=dummy->next;while(cur!=nullptr){if(s.count(cur->val)){pre->next=cur->next;cur = pre->next;}else{cur=cur->next;pre=pre->next;}}return dummy->next;
}

1.2.3刪除和為0的節點【前綴和】

前綴和的原理：

反復刪去鏈表中由 總和值為0 的連續節點組成的序列，直到不存在這樣的序列為止。

ListNode* removeZeroSumSublists(ListNode* head) {ListNode* dummy=new ListNode(0,head);//哈希表存儲前綴和，以及最后出現的節點unordered_map<int,ListNode*> mp;int prefixsum=0;ListNode* p=dummy;while(p!=nullptr){prefixsum += p->val;mp[prefixsum]=p;// 相同前綴和會覆蓋，保留最后一個p=p->next;}//第二次遍歷prefixsum=0;p=dummy;while(p!=nullptr){prefixsum+=p->val;p->next=mp[prefixsum]->next;p=p->next;}return dummy->next;
}

1.3改（交換節點）

序號	題目	鏈接
1	鏈表中的下一個最大節點	https://leetcode.cn/problems/next-greater-node-in-linked-list/description/?envType=problem-list-v2&envId=linked-list
2	刪除右側有一個更大數值的節點	https://leetcode.cn/problems/remove-nodes-from-linked-list/?envType=problem-list-v2&envId=linked-list
3	交換K和倒數第K個節點	https://leetcode.cn/problems/swapping-nodes-in-a-linked-list/description/?envType=problem-list-v2&envId=linked-list
4	合并0之間的節點	https://leetcode.cn/problems/merge-nodes-in-between-zeros/description/?envType=problem-list-v2&envId=linked-list

1.3.1鏈表中的下一個最大節點

遍歷整個鏈表，找到第一個比當前值大的元素。沒有則為0。

解法1：

• p指向當前節點
• q指向當前節點的下一個節點。q向后移動直到找到第一個比p值大的節點，添加到數組中。

vector<int> nextLargerNodes(ListNode* head) {vector<int> result;ListNode* p=head;while(p!=nullptr){ListNode* q=p->next;int maxval=0;while(q!=nullptr){if(q->val > p->val){maxval=q->val;break;//找到第一個最大的就退出}q=q->next;}result.push_back(maxval);p=p->next;}return result;
}

解法2：單調棧。
右側和更大可以使用單調棧。單調棧的關鍵是維持棧內元素的單調性。
棧中每個索引對應的 values 值從棧底到棧頂逐漸變小。

vector<int> nextLargerNodes(ListNode* head) {//將鏈表轉換為數組vector<int> values;ListNode* p=head;while(p!=nullptr){values.push_back(p->val);p=p->next;}//初始化結果數組int n=values.size();vector<int> result(n,0);//單調棧stack<int> st;for(int i=0;i<n;i++){//將要出棧的元素全部出完while(!st.empty() && values[i] > values[st.top()]){int idx=st.top();st.pop();result[idx]=values[i];}//棧空 || 當前值<棧頂值——入棧st.push(i);}return result;
}

1.3.2刪除右側有一個更大數值的節點

當前值與后面值比較：若存在一個值 > 當前值，將當前值刪掉。
思路與上述的單調棧差不多。重點在于棧內存儲的是節點，最后返回時候需要使用頭插法進行連接。

ListNode* removeNodes(ListNode* head) {stack<ListNode*> st;ListNode* p=head;while(p!=nullptr){//單調棧while(!st.empty() && p->val > st.top()->val){st.pop();}st.push(p);p=p->next;}//單調棧的元素“底大頂小”，因此實際需要從頭向下連接//重構鏈表ListNode* dummy=new ListNode();ListNode* q=dummy;while(!st.empty()){ListNode* node=st.top();st.pop();// 將當前節點插入到dummy和dummy->next之間node->next = dummy->next;dummy->next = node;}return dummy->next;
}

1.3.3交換K和倒數第K個節點

ListNode* swapNodes(ListNode* head, int k) {ListNode* dummy=new ListNode(0,head);//求鏈表的長度int length=0;ListNode* cur=head;while(cur!=nullptr){cur=cur->next;length++;}//找到第k個節點p，下標為k-1ListNode* p=dummy;for(int i=0;i<=k-1;i++){p=p->next;}//找到倒數第k個節點q，下標為length-kListNode* q=dummy;for(int i=0;i<=length-k;i++){q=q->next;}//交換swap(p->val,q->val);return head;
}

1.3.4合并0之間的節點

ListNode* mergeNodes(ListNode* head) {//新建一個鏈表ListNode* dummy=new ListNode(0);ListNode* cur=dummy;int sum=0;ListNode* p=head->next;while(p!=nullptr){if(p->val!=0){sum += p->val;}else{ListNode* newnode=new ListNode(sum);cur->next=newnode;cur=cur->next;sum=0;}p=p->next;}return dummy->next;;
}

1.4其他

序號	題目	鏈接
1	鏈表組件	https://leetcode.cn/problems/linked-list-components/description/?envType=problem-list-v2&envId=linked-list
2	螺旋矩陣	https://leetcode.cn/problems/spiral-matrix-iv/description/?envType=problem-list-v2&envId=linked-list
3	臨界值間的距離	https://leetcode.cn/problems/find-the-minimum-and-maximum-number-of-nodes-between-critical-points/description/?envType=problem-list-v2&envId=linked-list

1.4.1鏈表組件

int numComponents(ListNode* head, vector<int>& nums) {// 將nums中的值存入哈希集合，便于快速查找unordered_set<int> numSet(nums.begin(), nums.end());int count=0;int flag=0;ListNode* p=head;while(p!=nullptr){//當前節點值在nums中if(numSet.count(p->val)){//之前沒碰到過：新的組件if(!flag){count++;flag=1;}}//當前節點值不在nums中else{ flag=0;}p=p->next;}return count;
}

1.4.2螺旋矩陣

給你兩個整數：m 和 n ，表示矩陣的維數。
另給你一個整數鏈表的頭節點 head 。
請你生成一個大小為 m x n 的螺旋矩陣，矩陣包含鏈表中的所有整數。鏈表中的整數從矩陣 左上角 開始、順時針 按 螺旋 順序填充。如果還存在剩余的空格，則用 -1 填充。

模擬螺旋填充的過程：

• 螺旋填充的路徑是 “右→下→左→上” 的循環，每次完成一圈后縮小邊界。
  • 從左到右填充上邊界，完成后上邊界下移
  • 從上到下填充右邊界，完成后右邊界左移
  • 從右到左填充下邊界（如果還有空間），完成后下邊界上移
  • 從下到上填充左邊界（如果還有空間），完成后左邊界右移
• 用四個變量控制當前填充的邊界：上邊界 (top)、下邊界 (bottom)、左邊界 (left)、右邊界 (right)
• 從鏈表中依次取元素，按照螺旋路徑填充，直到所有元素用完或矩陣填滿

vector<vector<int>> spiralMatrix(int m, int n, ListNode* head) {// 初始化m×n矩陣，全部填充為-1vector<vector<int>> matrix(m, vector<int>(n, -1));//定義邊界int top=0;int bottom=m-1;int left=0;int right=n-1;//ListNode* current=head;while(current!=nullptr && top <= bottom && left <= right){// 1. 從左到右填充上邊界for (int col = left; col <= right && current != nullptr; col++) {matrix[top][col] = current->val;current = current->next;}top++; // 上邊界下移，該排已填滿// 2. 從上到下填充右邊界for (int row = top; row <= bottom && current != nullptr; row++) {matrix[row][right] = current->val;current = current->next;}right--; // 右邊界左移，該列已填滿// 3. 從右到左填充下邊界（需確保還有未填充的行）if (top <= bottom) {for (int col = right; col >= left && current != nullptr; col--) {matrix[bottom][col] = current->val;current = current->next;}bottom--; // 下邊界上移，該排已填滿}// 4. 從下到上填充左邊界（需確保還有未填充的列）if (left <= right) {for (int row = bottom; row >= top && current != nullptr; row--) {matrix[row][left] = current->val;current = current->next;}left++; // 左邊界右移，該列已填滿}}return matrix;
}

1.4.3臨界值的距離

模擬即可：

• 使用三個指針prev、curr和next分別指向當前節點的前一個節點、當前節點和后一個節點。
• 對于每個節點，檢查它是否是局部極大值點（大于前后節點）或局部極小值點（小于前后節點）。
• 記錄所有臨界點的位置索引（從 1 開始計數）。
• 計算出最小距離和最大距離。

vector<int> nodesBetweenCriticalPoints(ListNode* head) {if(head==nullptr || head->next==nullptr) return{-1,-1};vector<int> result;ListNode* pre=head;ListNode* cur=head->next;ListNode* next=cur->next;int pos=1;while(next!=nullptr){int ismax=(cur->val > pre->val) && (cur->val > next->val);int ismin=(cur->val < pre->val) && (cur->val < next->val);if(ismax || ismin) result.push_back(pos);//每一組極值pre=cur;cur=next;next=next->next;pos++;}if(result.size()<2) return {-1,-1};//計算最小距離（相鄰臨界點之間的最小距離）int mind=INT_MAX;for(int i=1;i<result.size();i++){mind=min(mind,result[i]-result[i-1]);}//最大距離（第一個和最后一個極值的距離）int maxd=result.back()-result.front();return {mind,maxd};
}