数据结构——线性表（链表，力扣中等篇，增删查改）

一、增删查改

1.1增（插入节点）

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.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.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-1
    ListNode* p=dummy;
    for(int i=0;i<=k-1;i++){
        p=p->next;
    }
    //找到倒数第k个节点q，下标为length-k
    ListNode* 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.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矩阵，全部填充为-1
    vector<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};
}