顺序表逆序与删除特定值：双指针与原地过滤核心解析

顺序表这两个操作，我敢说是数据结构笔试里出现频率最高的基础题，没有之一。逆序操作考的是你有没有真正理解“就地修改”的含义，删除特定值考的是你对元素移动和边界条件的敏感度。笔记写到第三篇，正好就是这两个最经典的“练手题”，很多同学在草稿纸上画得头头是道，一到手写代码就漏掉 length 更新、忘记判空指针、甚至把复杂度写成 O(n²) 而不自知。这篇我把两种操作的完整思路、代码实现、复杂度对比和调试经验一次讲透，希望能帮正在复习数据结构的大学生、准备面试跳槽的开发者少走几个月的弯路。

1. 顺序表与线性表基础：为什么这两题如此经典

1.1 顺序表存储结构快速回顾

顺序表本质上是线性表的顺序存储结构，底层就是一块连续的内存空间，靠数组来实现。用 C 语言描述时，通常有两种形态：静态数组和动态数组。静态数组容量固定，写题时最省事：

#define MAXSIZE 100 typedef struct { int data[MAXSIZE]; int length; } SeqList;

动态数组则需要用指针配合 malloc/realloc 管理堆内存，适合处理不确定规模的数据，后续我会重点推荐这种结构，因为它在面试和工程场景里更实用。

typedef struct { int *data; int length; int capacity; } SeqList;

不管你用哪种形态，必须牢记一个核心事实：顺序表靠下标访问，物理相邻就是逻辑相邻。这意味着你要插入或删除一个元素，后面的元素必须整体移动。这也是整个顺序表操作时间复杂度的根源——算法都是 O(n)，但常数系数差别很大，而这恰好是优化空间所在。

1.2 为什么偏偏是“逆序”和“删除特定值”这两个操作

逆序操作最考验你对双下标的控制力。它既要求你原地完成，又要求你不能额外开一个数组。很多新手第一反应是新建一个等长数组倒着拷贝，这在工程上当然可行，但在笔试场景里空间复杂度就直接扣分，而且在某些嵌入式或内存受限的环境里，额外 O(n) 空间是无法接受的。

删除特定值操作则完全不同，它考的是“如何用一次线性扫描完成原地过滤”。如果只会每次删除都调用一次“按位置删除”，时间复杂度会立刻恶化为 O(n²)。面试官特别喜欢追问这一点，因为很多人在平时作业里用 O(n²) 写法也能跑通，但一旦数据量到十万级就原形毕露。

这两个操作放在一起学习，恰好能帮你建立顺序表操作的完整直觉：逆序是控制下标，删除是控制写入位置。这两件事吃透了，后面再学有序表的合并、去重、插入排序都会轻松很多。

2. 顺序表逆序操作的完整拆解：双指针与边界控制

2.1 最优雅的写法：原地双指针交换

逆序的逻辑非常简单：用一个左指针指向表头，一个右指针指向表尾，两个指针相向移动，交换指向的元素，直到左指针超过右指针。

void reverseSeqList(SeqList *list) { if (list == NULL || list->length < 2) { return; } int i = 0; int j = list->length - 1; while (i < j) { int temp = list->data[i]; list->data[i] = list->data[j]; list->data[j] = temp; i++; j--; } }

这段代码的精髓在于循环条件i < j。当表长为奇数时，中间那个元素最终会和自身相遇，不需要交换；当表长为偶数时，最后两个元素会在相邻位置完成交换后使i > j，循环自然终止。

2.2 为什么不能直接在函数里新建一个数组再拷贝

如果你在函数内部写了这样一段代码：

int *temp = (int *)malloc(sizeof(int) * list->length); // 倒着拷贝 // 再正着拷回去 free(temp);

从结果上看，它确实完成了逆序，时间复杂度也是 O(n)，但空间复杂度变成了 O(n)，白白多了一次遍历和整块内存申请/释放的开销。在面试场景中，面试官追问的第一句往往是“能不能不用额外空间”，然后就会引导你写出双指针版本。

这就是典型的“知道原理但没形成肌肉记忆”的问题。我在模拟项目X的前期版本里就见过类似的代码，当时数据规模还小，性能差异看不出来，后来数据量涨到几十万，内存占用立刻翻倍，被迫重构。

2.3 逆序操作的边界条件与易踩的坑

逆序操作看着简单，实际手写时至少有三个高频错误。

第一是忘记判空。list为NULL时直接访问list->length会崩溃，这在真实面试里是非常低级的失误。

第二是空表或单元素表。length < 2时逆序毫无意义，让函数直接返回即可。有些同学不写这个判断，循环条件i < j本身也能兜住，但代码会显得不够严谨。

第三是循环写成i <= j。对于奇数长度的表，最后i == j时交换的是同一个元素，虽然结果不错，但多了一次无意义的自交换，而且在某些以“判断是否符合预期”的面试题中，这会被判定为边界处理不干净。

提示：手写逆序时，先画一个长度为 4 和长度为 5 的用例，分别走一遍指针轨迹，再落笔写代码，基本不会错。

2.4 扩展思考：如果要求“逆序后返回新表”怎么办

有些面试题不会让你原地逆序，而是要求返回一个新表，原表保持不变。这种场景下，真正的考点变成了“你能否准确区分浅拷贝和深拷贝”。正确写法是新建一个顺序表，从原表尾部向前遍历，把元素依次插入新表。时间复杂度 O(n)，空间复杂度 O(n)。

写法本身不复杂，但有一个细节：如果新表只分配了指针而没有分配数据空间，或者直接把data指针指过去，就会出现两个表共享同一块内存的诡异现象，原表一变，新表也跟着变。这个问题在课后作业里极少暴露，但在面试白板题中却容易被追问。

3. 删除特定值操作：从最朴素到最优雅

3.1 朴素但容易踩坑的“逐次删除”

最直观的思路是：遍历顺序表，找到值等于value的元素，就把后面所有元素往前移一格，然后length--。写成代码大概是这样：

void removeByValueNaive(SeqList *list, int value) { if (list == NULL) { return; } for (int i = 0; i < list->length; i++) { if (list->data[i] == value) { for (int j = i; j < list->length - 1; j++) { list->data[j] = list->data[j + 1]; } list->length--; i--; // 因为当前位置被替换了，需要重新检查 } } }

这段代码功能上没问题，但存在一个明显的性能隐患：如果表中有很多个等于value的元素，每次删除都要移动后面一大片元素，最坏情况下时间复杂度会退化到 O(n²)，比如表中全部元素都是value，每删一个都要把剩余元素全部前移一遍。

有人会问：那我在内层循环移动完之后执行i--，对不对？逻辑上是对的，否则会跳过一个元素。但这个细节很容易被遗漏，一旦漏掉，就会导致相邻的连续目标值检测不到，出现“删不全”的诡异现象。

3.2 高效写法：一次遍历完成原地过滤

真正高效的做法是使用“读写指针”的思路。读指针i负责从头到尾扫描原始元素，写指针newIndex负责记录下一个可写入的位置。只要当前元素不等于value，就把它写到newIndex处，然后newIndex加一。

void removeAllByValue(SeqList *list, int value) { if (list == NULL) { return; } int newIndex = 0; for (int i = 0; i < list->length; i++) { if (list->data[i] != value) { list->data[newIndex] = list->data[i]; newIndex++; } } list->length = newIndex; }

这个写法只有一个循环，每个元素最多被访问两次（一次作为list->data[i]读取，一次作为list->data[newIndex]写入），整体时间复杂度严格为 O(n)，空间复杂度 O(1)。

很多同学第一次看到这个写法时会疑惑：newIndex会不会覆盖还没有扫描到的元素？答案是不会。因为newIndex永远不超过i，写指针永远不会越过读指针，所以即使前面有被删除的元素产生空位，后续的非目标值也只是把这些空位填上，绝不会破坏尚未扫描的区域。

3.3 我为什么推荐“先记位置，再统一删除”的变体

有些场景下你并不想直接覆盖元素，比如需要统计删除了多少个元素，或者在删除前要对每个目标值做额外处理。此时可以把朴素的“边扫边删”改成“两遍遍历”：第一遍统计目标值数量，第二遍逐个覆盖。

void removeAllByValueTwoPass(SeqList *list, int value) { if (list == NULL) { return; } int count = 0; for (int i = 0; i < list->length; i++) { if (list->data[i] == value) { count++; } } int newIndex = 0; for (int i = 0; i < list->length; i++) { if (list->data[i] != value) { list->data[newIndex++] = list->data[i]; } } list->length = newIndex; }

这种写法虽然也比 O(n) 多遍历了一次，但胜在思路清晰，尤其适合在代码里加注释解释“先统计再搬运”的过程。如果你的目标是教学演示，两遍遍历反而更容易让学生理解。

3.4 多种删除特定值方案的复杂度与适用性对比

从表格可以清楚看到，原地过滤在所有非变态场景下都是最优解。面试时如果你先写朴素版，再主动优化到原地过滤，通常会留下不错的印象。

3.5 删除特定值操作中的几个易错细节

第一个易错细节是忘记更新length。很多初学者只把数据搬完，却忘了把list->length设为newIndex，导致打印时把尾部残留的旧值也打印出来。比如原来的表是{1, 2, 3, 2, 4}，删除 2 后，底层数组变成了{1, 3, 4, 2, 4}，如果不更新length，打印结果就成了{1, 3, 4, 2, 4}，看起来完全没删干净。

第二个易错细节是不小心把“按值删除”和“按位置删除”混用。按位置删除是deleteAt(list, pos)，它需要把pos后面的元素整体前移；按值删除则完全不需要在意具体位置，只关心“保留不等于 value 的元素”。如果混在一起写，代码会变得非常绕，还容易引入越界问题。

第三个细节是关于重复目标值的处理。面试官经常把问题升级为“删除所有值为 value 的元素”，和“只删除第一个值为 value 的元素”两个版本。前者就是本文的重点，后者只需要找到第一个匹配位置后调用一次按位置删除即可。写题之前一定要看清楚题干是“删除所有”还是“删除一个”，这两个答案完全不同。

4. 完整可运行代码：统一封装与健壮性设计

4.1 结构体定义与初始化

只看核心算法还不够，实际笔试或机试时，你往往需要完成一整套顺序表操作。我建议所有动态顺序表都按下面这种风格封装，既能保证内存安全，又能方便调试。

#include <stdio.h> #include <stdlib.h> #include <stdbool.h> typedef struct { int *data; int length; int capacity; } SeqList; bool initSeqList(SeqList *list, int capacity) { if (list == NULL || capacity <= 0) { return false; } list->data = (int *)malloc(sizeof(int) * capacity); if (list->data == NULL) { return false; } list->length = 0; list->capacity = capacity; return true; }

初看只是普通的 malloc，但有几个细节值得注意。第一，函数返回 bool 而不是 void，这样调用方能感知初始化是否失败；第二，capacity <= 0直接拒绝，避免出现容量为 0 或负数的非法状态；第三，一旦 malloc 失败，要把data明确设为NULL，避免产生悬挂指针。

4.2 动态扩容与时内存管理

顺序表最常见的隐患就是在插入时没有检查容量。很多新手写插入操作时直接list->data[list->length++] = value;，一旦插入次数超过capacity，就会写越界，破坏堆内存。

一个简单可靠的扩容策略是每次翻倍，这是最常见的摊销常数时间策略。

bool ensureCapacity(SeqList *list) { if (list == NULL || list->data == NULL) { return false; } if (list->length < list->capacity) { return true; } int newCapacity = list->capacity * 2; int *newData = (int *)realloc(list->data, sizeof(int) * newCapacity); if (newData == NULL) { return false; } list->data = newData; list->capacity = newCapacity; return true; }

使用realloc而不是“malloc + free + 赋值”的好处是：当扩容失败时，原指针仍然有效，不会出现数据丢失。这里有一个经典坑：千万不要写成list->data = (int *)realloc(list->data, ...)然后不检查返回值，因为一旦realloc失败，原指针已经被置空，原来的数据就彻底丢了。

提示：正规工程中还会引入缩容策略，比如当length远小于capacity时释放一部分内存，但笔试和面试一般不要求缩容，能把扩容写清楚已经很加分。

4.3 按位置删除的基础实现

虽然按值删除用不到按位置删除，但实现一次deleteAt有助于加深对“删除”这一概念的理解，也能在需要“只删第一个匹配值”时直接复用。

bool deleteAt(SeqList *list, int pos) { if (list == NULL || pos < 0 || pos >= list->length) { return false; } for (int i = pos; i < list->length - 1; i++) { list->data[i] = list->data[i + 1]; } list->length--; return true; }

这个函数暴露了顺序表删除操作最根本的特征：删除的代价主要来自“把后面的元素全部前移”。面试官问你“顺序表删除元素的时间复杂度是多少”时，你如果直接回答 O(1)，那就错了，因为需要先查找，查找 O(n) 是绕不开的。

4.4 打印与销毁辅助函数

拆解问题的时候，我强烈建议每个操作都用一个小函数去测试，不要一股脑写在一个 main 里。打印函数和数据装载函数是最常用的辅助工具。

void printSeqList(SeqList *list) { if (list == NULL) { printf("NULL\n"); return; } if (list->length == 0) { printf("[]\n"); return; } printf("["); for (int i = 0; i < list->length; i++) { printf("%d", list->data[i]); if (i < list->length - 1) { printf(", "); } } printf("]\n"); } void destroySeqList(SeqList *list) { if (list == NULL) { return; } free(list->data); list->data = NULL; list->length = 0; list->capacity = 0; }

打印函数中list->length的检查至关重要。若不小心用capacity去遍历，就会打印出已经“逻辑删除”的残留数据，看起来像是程序出 bug，其实是遍历边界用错了变量。

4.5 组装成完整的测试程序

写完之后，建议用一个短小的测试程序把每个功能都过一遍：

int main() { SeqList list; if (!initSeqList(&list, 4)) { return 1; } ensureCapacity(&list); list.data[list.length++] = 3; list.data[list.length++] = 1; list.data[list.length++] = 2; list.data[list.length++] = 2; list.data[list.length++] = 5; printSeqList(&list); reverseSeqList(&list); printSeqList(&list); removeAllByValue(&list, 2); printSeqList(&list); destroySeqList(&list); return 0; }

注意，这里的示例为了演示直接给data赋值，实际工程中应该封装成insertTail。不过这并不影响我们验证核心算法的正确性。

5. 常见问题与排查技巧实录

5.1 典型问题速查表

第三行的越界问题特别容易发生在“按位置删除”的代码里。写了for (int i = pos; i < list->length; i++)，然后把list->data[i] = list->data[i+1]放在循环里，当i = length - 1时访问data[length]，越界。这类问题在解题时很难通过小数据发现，因为系统不会每次都报错，往往在 data 量稍大时才随机崩溃。

5.2 调试顺序表操作的两个独门技巧

第一个技巧是“打印指针轨迹”。在逆序操作的循环里临时加一句printf("i=%d, j=%d\n", i, j);，就能清楚看到左右指针的移动过程。很多同学画图时很明白，但代码里看到i < j和i <= j的区别时犯迷糊，打印一次轨迹就豁然开朗。

第二个技巧是“用哨兵值标记删除目标”。如果要删除的是值 2，而你的测试数据里恰好也有 1、2、3，很容易把下标和值弄混。我常用的办法是把测试数组改成{10, 2, 3, 2, 5}，让每个元素有足够区分度，然后逐个排除。

5.3 从“能跑通”到“禁得住追问”的经验

我在某次课程设计中批过不少同学的代码，发现一个规律：能跑通的人很多，能回答清楚“为什么这个删除操作不会覆盖未扫描元素”的人很少。

被问到这个问题时，合格的回答是这样的：“因为写指针 newIndex 永远小于等于读指针 i，所以写入位置最多就是当前扫描位置，不会碰到还没扫描到的区域。换句话说，前面删掉多少元素，后面就往前补多少空位，永远不会超前。”

这个解释很简单，但体现的是对算法本质的理解。面试官真正想看到的不是代码默写能力，而是你能不能把一个 O(n) 的原地算法讲得明明白白。

6. 面试与应试高频追问清单

6.1 复杂度追问：逆序和删除的时间、空间复杂度分别是多少

最基础的追问必然是这两个：

• 逆序操作：时间复杂度 O(n)，因为每个元素最多被交换一次；空间复杂度 O(1)，因为没有使用额外空间。
• 删除所有特定值：一次遍历原地过滤的时间复杂度 O(n)，空间复杂度 O(1)；朴素逐次删除的最坏时间复杂度 O(n²)。

这里常犯的错误是把顺序表逆序的时间复杂度记成 O(n/2)，以为除以 2 就是不一样的数量级。面试官想要的答案是 O(n)，因为时间复杂度忽略常数系数。你可以口头上说明“实际是 n/2 次交换”，但最终复杂度必须写 O(n)。

6.2 变体追问：如果有序表中有重复元素，如何删除所有重复值

这道题的经典解法是“双指针去重”。因为表已经有序，相同元素必然相邻，所以可以利用一个写指针，把每一个与前一个元素不同的元素保留下来。核心代码非常短：

void removeDuplicatesSorted(SeqList *list) { if (list == NULL || list->length < 2) { return; } int newIndex = 1; for (int i = 1; i < list->length; i++) { if (list->data[i] != list->data[newIndex - 1]) { list->data[newIndex++] = list->data[i]; } } list->length = newIndex; }

这个问题的核心思路和删除特定值完全同源：用写指针保存结果，用读指针遍历原表。区别只在于比较条件从“是否等于 value”变成了“是否等于上一个保留值”。

6.3 结构追问：为什么顺序表删除元素是 O(n)，而链表删除是 O(1)

这个追问很常见，但很多人回答不完整。正确表述应该是：如果已经拿到了待删除结点的前驱指针，链表删除操作本身确实可以做到 O(1)，因为你只需修改前驱结点的next指针；但如果只给一个要删除的结点指针，而没有前驱指针，单链表仍然需要遍历找到前驱，复杂度就是 O(n)。

顺序表则不同，即使你已经知道删除位置，也需要把该位置后面的所有元素往前移动一格，平均移动 n/2 个元素，所以按位置删除本身就至少是 O(n)，没有“拿到位置就 O(1)”的说法。

6.4 面试追问：逆序后还能保持稳定性吗

问题乍一听有点怪，但确实会有面试官问。标准的稳定排序定义是：相同元素在排序前后的相对顺序不变。而顺序表逆序会把整个序列颠倒，如果表内有相同元素，它们的相对顺序必然会反转。所以答案是：逆序操作天生不稳定，且不要求稳定。

如果你写的逆序算法涉及分组反转或跳跃式交换，还需要额外解释清楚为什么仍然破坏了稳定性。这块知识点一般不会单独考，但和排序算法的稳定性结合起来考时，很多人容易懵。

6.5 408 与考研风格的常见考法

考研数据结构里，这类题通常会直接让你设计算法并分析复杂度。例如经典的“从顺序表中删除所有值为 x 的元素，要求时间复杂度 O(n)、空间复杂度 O(1)”，标准解法就是一次遍历原地过滤。

还有一种考法是“从有序顺序表中删除所有其值重复的元素，使表中所有元素的值均不同”。表面看是“删除重复”，实际上就是上一小节的双指针去重。遇到这种题，先判断“是否有序”，这直接决定解法复杂度。如果表无序，删除重复值需要先排序，复杂度会上到 O(n log n)；如果表有序，O(n) 就能解决。

7. 实操总结与经验心得

这些代码和算法，最终还是要落到一场真实的笔试或面试中。我个人比较推荐的学习路径是：看完文章后先合上电脑，在纸上手写一遍逆序，再手写一遍删除特定值，最后再对照测试用例运行。所有的边界条件都必须亲自踩过一遍，才可能形成肌肉记忆。

测试用例建议以纯文本形式记录，方便随时运行。比如：

• 空表：[]
• 单元素表：[5]
• 目标值在开头：[2, 1, 3]，删除 2
• 目标值在中间：[1, 2, 3]，删除 2
• 目标值连续出现：[1, 2, 2, 2, 3]，删除 2
• 全表都为目标值：[2, 2, 2]，删除 2

按这个清单测试，基本能覆盖 95% 以上的边界条件。如果哪个用例没通过，大概率就是前面速查表里提到的某类问题。

最后再分享一个小技巧：写完逆序和删除后，顺手把“按位置删除”和“有序去重”也写一遍。这四个函数放到同一个头文件里，以后参加笔试或机试时，能在五分钟内快速搭建出顺序表基础操作框架，剩下的时间就可以安心去写更复杂的算法了。

这两道题的价值不在于代码本身多么惊艳，而在于它们是很多复杂题目的地基。等你以后处理有序表合并、滑动窗口、甚至某些哈希表设计时，会发现当年练过的双指针和原地覆盖思想一直都在那里，只是换了一身衣服。