C++程序在给定约束条件下删除链表中给定节点

介绍

链表是一种常用的数据结构，在程序设计中经常会用到。删除链表中的特定节点是链表操作中的一个基本操作，但有时候我们需要在一定的约束条件下来删除节点，这就需要我们对于链表的相关知识有深入的了解，下面我们来具体介绍。

约束条件

在链表中删除节点，最常见的是对于链表中指定节点的删除，但实际的工程中，往往需要在一定的约束条件下来进行删除操作。

在本文中，我们约定删除约束条件如下：
* 节点必须为非首节点，即链表不为空；
* 节点的值必须等于给定的数据。

实现步骤

为了满足给定约束条件，我们需要先进行链表的查找操作，找到给定数据的节点。如果链表为空，则无法进行删除操作，直接返回即可；如果节点为首节点，则需要将链表头节点进行修改，具体实现如下：

#include<bits/stdc++.h>  // 头文件
using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {} // 构造函数
};

ListNode* deleteNode(ListNode* head, int val) {
    if(!head) return nullptr; // 若链表为空，直接返回
    if(head->val==val) return head->next; // 若为首节点，需要修改链表头
    ListNode *pre = head, *cur = head->next; // 初始化pre和cur
    while(cur && cur->val!=val) pre=cur, cur=cur->next; // 查找节点
    if(cur) pre->next=cur->next; // 找到节点，进行删除操作
    return head;
}

这里我们采用C++的结构体定义链表，并在结构体中先定义好构造函数，为后续操作做好准备。然后在函数中，我们首先对链表是否为空进行判断。若为空，则直接返回一个空指针。若不为空，再对链表的第一个节点是否为待删除节点进行判断，如果是，则将链表头指针向后移一位。对于其他情况下的节点删除，直接遍历链表找到该节点进行删除操作即可。

测试与样例

为验证我们写的函数是否符合题目要求，我们测试以下数据：

ListNode *head = new ListNode(1); // 创建带有头节点的链表
ListNode *p = head;
int n = 5, val = 3;
for (int i = 1; i <= n; ++i){
    ListNode *temp = new ListNode(i);
    p->next = temp, p = p->next;
}
head = deleteNode(head, val); // 删除指定值的节点
p = head;
while (p){
    cout << p->val << "\t";
    p = p->next;
}

该测试数据表示我们创建了一个以1为头节点，5个数为元素的链表。我们给定待删除的数为3，经过函数处理后打印出链表，输出如下：