王道数据结构2.2.3代码题精讲：顺序表与链表核心模板与易错点

如果你也在准备27考研、正在和王道《数据结构》复习指导硬碰硬，那么2.2.3这一节的课后代码题，尤其是（二）里的1~9题，应该已经在你的计划表上躺了很久了。别急着跳过，这几道题虽然看起来只是“线性表”的基础操作，但它们是整个408代码题的地基。顺序表删除、链表逆置、双指针覆盖、快慢指针判环……这些模板，几乎每年都会以不同的外衣出现在真题里。

我自己在二刷这组题的时候，说实话还是被几道题卡住了。卡住不是因为我不会写，而是因为我对边界条件的理解还不够细。读题时觉得“就这”，真上手写代码才发现到处都是坑。所以今天这篇就围绕王道2.2.3（二）1~9，把顺序表和链表两大类代码题的核心思路、可复现模板、易错点一次讲透，顺便聊聊这些课后题是怎么映射到408真题上的。

1. 为什么每个刷王道的人都要认真啃2.2.3（二）1~9

先聊一个很多人心里都有但没说出口的问题：这组题真的值得花大量时间吗？我的回答是，值得，而且非常值得。

王道的数据结构复习指导，本质上是一本“把408考点浓缩到能背完”的辅导书，2.2.3这一节的课后代码题，正好卡在线性表这个最基础、也最爱出代码题的章节。408的算法设计题，要么直接考线性表，要么把线性表作为更高阶题目的前置工具。比如后面树、图里的大量操作，底层都是链表节点的移动、指针的修改。如果你在2.2.3这里没把“指针怎么指”“节点怎么断”“表长怎么更新”练出肌肉记忆，后面学树和图的代码题会非常痛苦。

（二）1~9这组题还有一个特殊价值：它把顺序表和链表的“常规操作”压缩成了几个典型场景。删除指定值、删除区间值、有序去重、有序合并、逆置、循环移位、查找插入、链表删除、链表逆置、找公共节点、判环……这些场景单独看都不难，但组合起来就是408大题的套路。很多真题看起来花里胡哨，你拆开后发现不过是“先逆置再删除”“先找位置再插入”的缝合。

我更想强调一点：这组题适合的复习阶段，不是最后冲刺，而是第一轮强化结束、第二轮刚开始的时候。因为你需要给自己留出足够的时间去“写错”“调试”“重写”。如果拖到10月才开始手写代码，你在考场上大概率只能写出框架，写不出正确细节。我自己就是第一轮看完视频觉得全会，到第二轮默写时才发现，很多代码的细节——比如删除连续重复元素时指针该不该动、递归删除链表时头指针要不要更新——全是模糊的。这些问题，只能在2.2.3的1~9题里提前暴露。

所以，这篇文章不是带你背代码，而是带你把代码背后的判断逻辑理清楚。后面的内容，你可以直接抄作业，但更建议你抄完自己再默写一遍。

2. 先从题目分类入手：这一组代码题到底在考什么

不同版本的王道书里，2.2.3（二）1~9的题号偶尔会调整，但考察范围基本稳定：顺序表为主，链表为辅。如果你手上的版本和我说的题号对不上，不用慌，按下面的类型去认领题目就行。

2.1 顺序表题：删除、去重、合并、移位，全是408常客

顺序表这部分，基本跑不出五种操作。

第一类，删除单个特定元素。比如删除顺序表中所有值等于x的元素，要求时间复杂度O(n)、空间复杂度O(1)。这题考的是“覆盖式删除”的思路，用双指针或者单指针加计数都行，核心是不能每删一个元素就把后面所有元素往前移，否则复杂度变成O(n²)。

第二类，删除某个值区间内的元素。比如删除所有值在s到t之间的元素，或者从有序表中删除这个区间。这里要注意s和t是否合法、是否包含边界值、题目说的是“值在区间内”还是“位置在区间内”，差一个字，代码就差一行。

第三类，去重和合并。有序表去重、两个有序表合并成一个有序表，这两个问题考查的是归并思想。去重本质上是一次遍历中“保留不同值”，合并则是双指针依次比较大小、谁小先放谁。代码本身不长，但要处理的细节不少，比如合并时表容量够不够、去重时首元素要不要单独处理。

第四类，逆置、交换、循环移位。比如将数组前m个元素和后n个元素整体互换，或者将数组循环左移p位。这类题的核心套路是“局部逆置+整体逆置”，一句话就能讲完，但能把边界写对的人不多。

第五类，查找与插入的组合。比如在递增有序表中查找x，找到就与后继交换，找不到就插入并保持有序。这题前半段可以用折半查找降低时间，后半段是顺序表插入的标准操作。它考的是“查找和插入如何衔接”，很多人折半写对了，插入位置算错了，low和high一混淆，整个就崩了。

2.2 链表题：删除、逆置、合并、判环，万变不离其宗

链表部分的1~9题，重点集中在单链表上。

删除类题目有两种变体：一种是带头结点，直接从头结点开始遍历，删除后继中符合条件的节点；另一种是不带头结点，需要递归或二级指针。递归删除不带头结点的链表，是很多人的盲区，因为递归参数如果传的是值传递，头指针根本不会被更新。

逆置类题目也有两种写法：一种是三指针迭代，把每个节点的next指向前驱；另一种是头插法，把当前节点逐个插到头结点后面。两种写法的效率差别不大，但考场上三指针更直观，头插法更简洁。我建议两种都练一遍，因为有些综合题需要你“部分逆置”，这时候你对指针走位的理解必须足够清楚。

除此之外，链表还爱考“找两个链表的公共后缀”“判断链表是否有环并找环入口”。这两道题是快慢指针和长度对齐的经典应用，思路很巧，但只要听过一次就不会忘。难的是代码实现时对空指针的判断，比如while循环里漏了fast->next这个条件，直接段错误。

2.3 动手前的三个前置知识

写这些代码题之前，有三个前置知识必须烂熟于心，否则写出来的代码很容易“自我感觉正确但跑不过”。

第一个是带头结点和不带头结点的区别。带头结点的链表有一个额外的虚拟头节点，所有插入删除操作都可以从L->next开始统一处理；不带头结点的链表，删除首节点时必须修改头指针本身。王道很多题的答案默认带头结点，但题目如果明确说“不带头结点”，你的代码就得换成另一种写法。

第二个是“引用传递”和“指针传递”的区别。在C++里，链表头指针经常写成LinkList &L，就是为了让函数内部能修改头指针。如果你写成LinkList L，函数内部对L的修改不会传回调用者。递归删除不带头结点的链表时，这个问题尤其致命。

第三个是时间复杂度与空间复杂度的限制。王道代码题几乎都会明确要求“时间O(n)、空间O(1)”，这意味着你不能开辅助数组、不能递归（递归栈算空间）、不能反复整体移动元素。很多同学思路没问题，但一写就违规，就是没把这个约束刻在脑子里。

3. 手把手过一遍核心代码：顺序表的五类模板

顺序表的代码题，本质上是在一个数组上做各种操作。虽然简单，但正因为简单，考官要求反而更高，边界必须一次写对。

3.1 双指针删除：所有等于x的元素，时间复杂度O(n)

先看最经典的“删除所有值为x的元素”。我见过很多人第一次写的是：遍历找到x，然后把后面的元素全部前移。这么做确实能删除，但最坏情况是数组里全是x，每删一个都要移动O(n)个元素，整体复杂度O(n²)，不合格。

正确做法是用一个慢指针k记录“最终要保留的位置”，用快指针i遍历原数组。只要当前元素不等于x，就把它放到k位置，然后k加一。等于x的元素直接跳过，相当于被“覆盖”掉了。

cpp复制bool deleteAllX(SqList &L, ElemType x) {
    if (L.length == 0) return false;

    int k = 0;
    for (int i = 0; i < L.length; i++) {
        if (L.data[i] != x) {
            L.data[k++] = L.data[i];
        }
    }

    L.length = k;
    return true;
}

这个代码很短，但三个细节要强调：第一，k从0开始，因为第一个元素也可能等于x，需要被覆盖；第二，判断条件是“不等于x才保留”，不是“等于x就删除”，这个逻辑不要写反；第三，最后必须更新L.length，否则表的长度还是原来的，虽然数组里残留了旧数据，但逻辑上没删干净。

这条双指针模板太重要了，后面的区间删除、去重，全是这个思路的变体。

3.2 区间删除和有序去重：同一个覆盖思路

删除值在s到t之间的所有元素，和上面几乎一模一样，只是保留条件从“不等于x”变成了“小于s或大于t”。

cpp复制bool deleteRange(SqList &L, ElemType s, ElemType t) {
    if (L.length == 0 || s >= t) return false;

    int k = 0;
    for (int i = 0; i < L.length; i++) {
        if (L.data[i] < s || L.data[i] > t) {
            L.data[k++] = L.data[i];
        }
    }

    L.length = k;
    return true;
}

注意一个陷阱：题目如果写的是“s到t之间”的整数，通常不明确包含s和t本身。王道题里的标准处理是按“s < 值 < t”还是“s <= 值 <= t”，你要看原题。我上面这个模板是删除闭区间[s, t]内的元素，如果你要做开区间，把判断条件改成 <= 和 >= 就行。考试时读题一定要看到底“等于”算不算。

有序顺序表去重，思路也类似。因为表已经有序，重复元素必然连续。用一个k记录当前不重复序列的末尾位置，从第二个元素开始遍历，只要当前元素和上一个保留元素不同，就保留。

cpp复制bool deleteDuplicates(SqList &L) {
    if (L.length <= 1) return true;

    int k = 1;
    for (int i = 1; i < L.length; i++) {
        if (L.data[i] != L.data[k - 1]) {
            L.data[k++] = L.data[i];
        }
    }

    L.length = k;
    return true;
}

这里有个小细节：k从1开始，因为第一个元素一定保留。比较的是L.data[k - 1]而不是L.data[i - 1]，如果写后者，遇到连续三个相同元素时，第三个会被误判为不同，导致去重失败。仅这一处不同，就是很多人代码跑不过的根源。

3.3 合并有序表：先把拷贝逻辑焊死

把两个有序顺序表合并成一个新的有序顺序表，这题我建议直接记模板。双指针i、j分别扫描表A、B，谁的当前元素小，谁就先放进结果表C；扫描完一个表后，把剩余元素全部拷进去。

cpp复制bool mergeSqList(SqList A, SqList B, SqList &C) {
    if (A.length + B.length > C.maxSize) return false;

    int i = 0, j = 0, k = 0;
    while (i < A.length && j < B.length) {
        if (A.data[i] <= B.data[j]) {
            C.data[k++] = A.data[i++];
        } else {
            C.data[k++] = B.data[j++];
        }
    }

    while (i < A.length) C.data[k++] = A.data[i++];
    while (j < B.length) C.data[k++] = B.data[j++];

    C.length = k;
    return true;
}

写这题时常见问题是忘记处理“剩余元素”，也就是A或B还没有遍历完的情况。另一个问题是合并前不检查C的容量，直接往里面写，导致越界。408考场上不会给你运行时环境，所以逻辑正确性比跑通更重要，容量检查建议写上，体现严谨。

如果你想背“为什么用<=”，是因为当两个元素相等时，我们希望先把A的元素放进去，保证合并后的表稳定。稳定不稳定对于排序题不关键，但对于后续“合并后求中位数”之类的扩展题，稳定会让你更好分析。

3.4 逆置/交换/循环移位：所有旋转题的核心

这块必须掌握一个工具函数：局部逆置。给定顺序表和左右边界，把这一段元素原地翻转。它是一切“交换两段”“循环移位”的基础。

cpp复制void reverse(SqList &L, int left, int right) {
    while (left < right) {
        ElemType temp = L.data[left];
        L.data[left] = L.data[right];
        L.data[right] = temp;
        left++;
        right--;
    }
}

假设顺序表里存了(a1,a2,...,am,b1,b2,...,bn)，现在要把后面的bn段换到前面来。标准做法是三次逆置：先整体逆置，再逆置前一段，再逆置后一段。网上有各种口诀，我怕你记混，直接看代码。

cpp复制// 将前 m 个元素和后 n 个元素互换，m + n == L.length
void exchangeAB(SqList &L, int m) {
    reverse(L, 0, L.length - 1);   // 整体逆置
    reverse(L, 0, L.length - m - 1); // 逆置前半段
    reverse(L, L.length - m, L.length - 1); // 逆置后半段
}

如果是循环左移p位，本质也一样：先把前p个元素逆置，再把剩余元素逆置，最后整体逆置。注意p要先对表长取模，因为左移n次等于没移。

cpp复制void rotateLeft(SqList &L, int p) {
    p = p % L.length;
    reverse(L, 0, p - 1);
    reverse(L, p, L.length - 1);
    reverse(L, 0, L.length - 1);
}

这类题最容易被扣分的地方是逆置边界。比如左移p个位置时，如果p等于0，三次reverse里会出现left > right的情况。好在我的reverse函数里while条件已经处理了空区间，所以p=0也能安全返回。但如果你的逆置函数没有这个保护，代码就会出问题。你可以在自己的模板里加一句if (left >= right) return;。

3.5 递增表中查找或插入：折半查找加插入模板

最后一类顺序表题，是在递增有序表中查找x，找到就和后继交换，找不到就插入并保持有序。这题的前半段“最少时间”提示你用折半查找，后半段是标准的顺序表插入。

cpp复制void searchInsert(SqList &L, ElemType x) {
    int low = 0, high = L.length - 1, mid;

    while (low <= high) {
        mid = (low + high) / 2;
        if (L.data[mid] == x) {
            if (mid < L.length - 1) {
                ElemType temp = L.data[mid];
                L.data[mid] = L.data[mid + 1];
                L.data[mid + 1] = temp;
            }
            return;
        } else if (L.data[mid] < x) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }

    // 未找到 x，此时 low 就是应该插入的位置
    for (int i = L.length; i > low; i--) {
        L.data[i] = L.data[i - 1];
    }
    L.data[low] = x;
    L.length++;
}

这个代码的难点是，为什么折半结束后插入位置是low而不是high。你可以这么记忆：while循环退出时，一定有low > high，并且low左边的元素都小于x，high右边的元素都大于x。所以x应该插在low位置。如果不理解，就拿一个具体例子手推一遍，比如L={1,3,5}，x=4，推完你就再也不会错了。

4. 链表代码题的高频模板，你看懂和写对之间缺的是什么

链表题比顺序表题难，难在指针操作不可见。你脑子里明明知道要怎么指，一写代码就不知道下一步该存哪个临时节点了。

4.1 带头结点链表的删除指定值：两步走

带头结点的单链表删除所有值为x的节点，核心是遍历时始终记录“前驱节点”。如果当前节点的后继等于x，就删掉它，但前驱指针不要动，因为后继可能还是x；如果当前节点的后继不等于x，前驱指针才往后走。

cpp复制void deleteNodeByValue(LinkList &L, ElemType x) {
    LNode *p = L; // p 始终是当前保留节点的前驱
    while (p->next != NULL) {
        if (p->next->data == x) {
            LNode *q = p->next;
            p->next = q->next;
            free(q);
        } else {
            p = p->next;
        }
    }
}

我最开始写这个题的时候，在if里多写了一句p = p->next，结果遇到连续两个x，第一个删完，p跑到第二个x后面去了，第二个x就漏删了。记住：删除操作发生后，p不要动，因为p->next已经更新，下一次循环自动检查新的后继节点。

如果是递归删除不带头结点的链表，写法是另一套。核心是递归返回值或引用传递，否则头指针改不动。

cpp复制void deleteValueRecursive(LinkList &L, ElemType x) {
    if (L == NULL) return;

    if (L->data == x) {
        LNode *p = L;
        L = L->next;
        free(p);
        deleteValueRecursive(L, x);
    } else {
        deleteValueRecursive(L->next, x);
    }
}

注意这里第一个参数必须是LinkList &L，也就是引用。如果写成LinkList L，删除第一个节点后，调用者手里的头指针仍然是原来那个被释放的地址，后面就全乱了。

4.2 就地逆置：三指针还是头插法？

原地逆置单链表，王道标准答案通常是三指针法。pre指向已逆置部分的头，cur指向当前要处理的节点，next保存cur的后继，防止断链。

cpp复制void reverseList(LinkList &L) {
    LNode *pre = NULL;
    LNode *cur = L->next;

    while (cur != NULL) {
        LNode *next = cur->next;
        cur->next = pre;
        pre = cur;
        cur = next;
    }

    L->next = pre;
}

三指针法的关键就是那句LNode *next = cur->next;必须放在修改cur->next之前。如果你先改了cur->next，后面的节点就找不到了。这个问题在考场上特别容易发生，因为人一紧张就容易把顺序写反。

还有一个更快的头插法：遍历原链表，把每个节点摘下来，插到头结点后面。头插法的代码更短，但对于初学者而言，容易搞混“当前节点”和“下一个节点”的保存顺序。二选一即可，我建议选三指针法，因为你后续做“部分逆置”时，三指针的思想更容易迁移。

4.3 找公共后缀和判环：快慢指针的变形

两个链表找公共后缀的节点，思路是先把两个链表对齐。因为公共后缀意味着末尾长度相等，较长的链表前段多出来的部分肯定是非公共的。算出两个表长，长的链表先走差值步，然后两个指针同步前进，第一次相遇的节点就是公共后缀起点。

cpp复制int getListLength(LinkList L) {
    int len = 0;
    LNode *p = L->next;
    while (p != NULL) {
        len++;
        p = p->next;
    }
    return len;
}

LNode* findCommonNode(LinkList A, LinkList B) {
    int lenA = getListLength(A);
    int lenB = getListLength(B);
    int diff = lenA > lenB ? lenA - lenB : lenB - lenA;

    LNode *pa = A->next;
    LNode *pb = B->next;

    if (lenA > lenB) {
        while (diff--) pa = pa->next;
    } else {
        while (diff--) pb = pb->next;
    }

    while (pa != NULL && pa != pb) {
        pa = pa->next;
        pb = pb->next;
    }
    return pa; // 没有公共节点时，返回的是 NULL
}

判环和找环入口也是经典。先用快慢指针判断有没有环：快指针每次走两步，慢指针每次走一步，如果两者相遇说明有环；如果快指针走到了空，说明无环。找到环入口的方法是：相遇后，把一个指针放回起点，另一个留在相遇点，然后两个指针都每次走一步，再次相遇的位置就是环入口。这个结论可以用路程关系推导，但考试时记住结论直接写就行。

cpp复制LNode* detectCycle(LinkList L) {
    LNode *fast = L, *slow = L;

    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) break;
    }

    if (fast == NULL || fast->next == NULL) return NULL;

    fast = L;
    while (fast != slow) {
        fast = fast->next;
        slow = slow->next;
    }
    return slow;
}

这段代码最容易被忽略的是第一个while条件。如果写成while (fast != NULL)，当fast走到链表末尾时，fast->next很可能就是空指针，下一轮循环就会出现空指针访问。所以fast != NULL && fast->next != NULL这个条件一个都不能少。

5. 刷这组题时我踩过的坑，以及怎么往408真题上迁移

代码题光讲模板是不够的，还必须讲坑。下面这些错误都是我实际写代码时犯过的，或者帮别人debug时见过的，每一条都值得你写进自己的错题本。

5.1 五个最容易犯的边界错误

我建议把这五条贴在你的笔记本旁边。很多408考生代码题丢分，丢的从来不是“会不会做”，而是“边界有没有想到”。

5.2 从课后题到真题：三个迁移思路

历年408代码大题，几乎都能从2.2.3这1~9题里找到原型。我总结了三个最常见的迁移方向。

第一个是“双指针删除”迁移到“扫描数组并保留满足条件的元素”。比如让你找出数组中所有非某值的元素、把所有偶数放到前面的操作，本质都是双指针覆盖和交换。你只要把if (data[i] != x)的保留条件改掉，就能解决半个数组题。

第二个是“三次逆置”迁移到“数组位置变换”。真题中出现的将序列循环左移、将两个线性表互换位置，都是这套模板。下次读到题目里出现“左移”“互换”“旋转”，第一反应就是调三个reverse，而不是真的去一个一个移动元素。

第三个是“快慢指针”迁移到“链表环和公共节点”。真题直接考过找环的变体，比如判断链表是否存在环、找入口节点。你只要把detectCycle这个函数默写熟，再结合链表长度统计，就能解决一大类链表综合题。

5.3 给27考研党的刷题建议

最后说点实际的复习建议。

第一，别只看答案。看答案会给你一种“我懂了”的错觉，但考场上你面对的是空白答题纸。我建议每道题都先在纸上默写完整代码，再和标准答案对照。如果默写不出来，隔天再默写一遍，直到能连续两遍无差错写出来为止。

第二，主动设计边界测试。自己写完代码后，用几个特殊用例去“跑”一遍：空表、只有一个元素、元素全是同一个值、元素首尾都要删除。你不需要真的在电脑上编译，只要在纸上模拟几行，就能发现大量逻辑漏洞。

第三，把复杂度写在每道题旁边。王道要求时空复杂度，这是阅卷人的给分点。每一个模板你都应该能说出时间复杂度为什么是O(n)、空间复杂度为什么是O(1)。说不上来，说明你还没真正理解这个算法。

第四，二刷时做“减法”。第一遍你靠模板堆，第二遍你应该把每个模板归结成一个场景。看到“删除所有符合某条件的元素”就想到双指针；看到“有序表合并”就想到归并；看到“左移右移”就想到三次逆置。这种条件反射才是你最终上考场需要的状态。

我个人在二刷这9道题的时候，最大的体会不是“我终于会用某种算法了”，而是“我终于知道为什么书上要这样写了”。如果你能在每个模板旁边留一行注释，写上这个操作在解决哪个边界问题，这组题就算真正吃透了。刷完之后你会发现，后面树、图里的代码题，很多都是线性表这些基本动作的换皮升级而已。把地基打牢，比盲目追求刷题数量重要得多。