夜雨聆风408 数据结构算法题，双指针法是当之无愧的「出题亲儿子」。
翻遍 2009 到 2024 的真题，每两三年就有一道双指针的大题。快慢指针、前后指针、三指针…… 换着花样考，但万变不离其宗。
今天这篇文章，我把历年真题中所有涉及双指针的大题全部拆一遍，从 2009 年的「链表倒数第 k 个结点」到 2020 年的「三元组最小距离」，五道经典真题，一题一题掰开揉碎了讲。
每道题都包含：题目还原 → 设计思想 → 完整代码 → 复杂度分析。建议收藏，考前反复看。
先搞清楚：什么是双指针法？
双指针法不是某个具体的算法，而是一类解题策略的总称。
核心思想很简单：用两个（或多个）指针在数据结构上按一定规则移动，在一次遍历内完成查找、重排、比对等操作。
在 408 真题中，双指针法主要有四种形态：
- 同向快慢指针
：两个指针同方向移动，一个快一个慢，保持固定间距 - 长度差 + 同步指针
：先让一个指针领先几步，然后同步移动 - 前后夹逼双指针
：一前一后向中间靠拢 - 多指针扩展
：三指针甚至更多，思想一脉相承
下面，按年份顺序逐一拆解。
2009 年第 42 题：单链表倒数第 k 个结点
题目还原
已知一个带有头结点的单链表，只给出了头指针 list。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第 k 个位置上的结点。若查找成功，输出该结点的 data 值并返回 1；否则返回 0。
破题思路
这道题是同向快慢指针最经典的入门题。
想象两个人在同一条跑道上跑步：一个人先出发跑了 k 米，然后第二个人再出发。等第一个人跑到终点时，第二个人离终点刚好就是 k 米 —— 也就是倒数第 k 个位置。
核心步骤：
快指针 fast和慢指针slow同时指向第一个数据结点快指针先走 k 步。走不到 k 步就空了？说明链表长度不够，直接返回失败 快慢指针同步向后移动，直到快指针到末尾（NULL） 此时慢指针所在位置，就是倒数第 k 个结点
代码实现
typedef struct Node { int data; struct Node *link; } LinkNode, *LinkList; int find_k(LinkList list, int k) { if (list == NULL || k <= 0) { return 0; // 参数非法 } LinkNode *fast = list->link; // 快指针 LinkNode *slow = list->link; // 慢指针 // 快指针先走 k 步 for (int i = 0; i < k; i++) { if (fast == NULL) { return 0; // 链表长度不足 k } fast = fast->link; } // 快慢指针同步移动 while (fast != NULL) { fast = fast->link; slow = slow->link; } printf(「%d」, slow->data); return 1; }时间复杂度：O(n)，仅遍历链表一次。空间复杂度：O(1)，只用了两个指针。
2012 年第 42 题：两个链表的公共后缀
题目还原
两个单词的字母用单链表存储，若它们有相同的后缀（如 「loading」 和 「being」 共享 「ing」），则后缀部分的结点是共享的。给定两个链表的头指针 str1 和 str2，设计一个时间上尽可能高效的算法，找出共同后缀的起始位置。
破题思路
这题的 trick 在于：两个链表长度可能不同，但公共后缀部分的长度一定相同。
所以思路分两步：
- 对齐起点
：先算两个链表的长度差 d，让长链表的指针先走 d 步 - 同步查找
：两个指针同步向后移动，当它们指向同一个结点时，就是公共后缀的起点
这本质上是「长度差 + 同步指针」的变体，核心还是双指针思想。
代码实现
typedef struct Node { char data; struct Node *next; } LinkNode, *LinkList; LinkNode* findCommon(LinkList str1, LinkList str2) { int len1 = 0, len2 = 0; LinkNode *p = str1->next; LinkNode *q = str2->next; // 计算两个链表的长度 while (p != NULL) { len1++; p = p->next; } while (q != NULL) { len2++; q = q->next; } // 长链表指针先走差值步 LinkNode *longp, *shortp; int d; if (len1 >= len2) { longp = str1->next; shortp = str2->next; d = len1 - len2; } else { longp = str2->next; shortp = str1->next; d = len2 - len1; } while (d--) longp = longp->next; // 同步遍历，寻找公共结点 while (longp != NULL && shortp != NULL) { if (longp == shortp) return longp; longp = longp->next; shortp = shortp->next; } return NULL; }时间复杂度：O(m + n)。空间复杂度：O(1)。
2019 年第 41 题：重排单链表
题目还原
线性表 L = (a₁, a₂, a₃, ..., aₙ₋₁, aₙ) 用带头结点的单链表存储。请设计一个空间复杂度 O(1) 的算法，将 L 重排为 L' = (a₁, aₙ, a₂, aₙ₋₁, a₃, aₙ₋₂, ...)。
简单说：第一个不动，最后一个插到第二个，倒数第二个插到第四个…… 首尾交替排列。
破题思路
这道题是双指针法的高阶综合应用，拆成三步：
- 快慢指针找中点
：快指针走两步，慢指针走一步。快指针到末尾时，慢指针刚好在中点 - 逆置后半段
：把中点之后的链表原地反转 - 交错合并
：前半段和逆置后的后半段交替拼接
每一步都是经典算法，组合在一起就能解决复杂问题。
代码实现
typedef struct node { int data; struct node *next; } NODE; void reorderList(NODE *head) { if (head == NULL || head->next == NULL) return; // 第一步：快慢指针找中点 NODE *slow = head, *fast = head; while (fast->next != NULL && fast->next->next != NULL) { slow = slow->next; // 慢指针走一步 fast = fast->next->next; // 快指针走两步 } NODE *mid = slow; // mid 为前半段尾结点 // 第二步：逆置后半段链表（头插法） NODE *p = mid->next; mid->next = NULL; // 断开前后两段 NODE *pre = NULL, *next; while (p != NULL) { next = p->next; p->next = pre; pre = p; p = next; } // 第三步：交错合并两个子链表 NODE *p1 = head->next; // 前半段头 NODE *p2 = pre; // 逆置后后半段头 NODE *temp1, *temp2; while (p1 != NULL && p2 != NULL) { temp1 = p1->next; temp2 = p2->next; p1->next = p2; p2->next = temp1; p1 = temp1; p2 = temp2; } }时间复杂度：O(n)，找中点、逆置、合并各遍历一次。空间复杂度：O(1)。
2020 年第 41 题：三元组最小距离
题目还原
定义三元组 (a, b, c) 的距离 D = |a-b| + |b-c| + |c-a|。给定三个非空升序数组 S₁、S₂、S₃，求所有可能三元组中的最小距离。
例如 S₁ = {-1, 0, 9}，S₂ = {-25, -10, 10, 11}，S₃ = {2, 9, 17, 30, 41}，最小距离为 2，对应三元组 (9, 10, 9)。
破题思路
这是双指针法的三指针扩展，思想一脉相承。
首先，距离公式可以化简：
D = |a-b| + |b-c| + |c-a| = 2 × (max(a,b,c) - min(a,b,c))
所以我们要做的，就是让最大值和最小值的差距尽可能小。
策略：三个指针分别指向三个数组的当前位置。每次计算距离后，把最小值对应的指针往后移 —— 因为最小值拖后腿，得把它变大，才能缩小差距。
代码实现
#include <limits.h> #include <math.h> int minDistance(int A[], int n1, int B[], int n2, int C[], int n3) { int i = 0, j = 0, k = 0; int minDist = INT_MAX; while (i < n1 && j < n2 && k < n3) { int a = A[i], b = B[j], c = C[k]; // 计算当前距离 int d = abs(a - b) + abs(b - c) + abs(c - a); if (d < minDist) minDist = d; // 移动最小值对应的指针 int minVal = a; if (b < minVal) minVal = b; if (c < minVal) minVal = c; if (minVal == a) i++; else if (minVal == b) j++; else k++; } return minDist; }时间复杂度：O(n₁ + n₂ + n₃)。空间复杂度：O(1)。
补充：2011 年第 42 题——两个有序数组的中位数
题目还原
两个等长的升序序列 A 和 B（各 n 个元素），求它们的所有元素合并后的中位数。
注意：本题的最优解是二分法（O(log n)），408 标准答案也这么给。但双指针法（O(n)）是更直观的解法，在考场上可以作为保底方案。
双指针解法思路
两个指针 i、j 分别指向 A、B 的起始位置。每次比较 A[i] 和 B[j]，较小值对应的指针后移，同时计数。当数到第 n 个元素时（中位数位置），即为所求。
int findMedian(int A[], int B[], int n) { int i = 0, j = 0, count = 0, result; while (count < n) { if (A[i] < B[j]) { result = A[i]; i++; } else { result = B[j]; j++; } count++; } return result; }五道真题一张表总结
三个备考建议
第一，套路比灵感重要。 双指针法考来考去就那几种套路，与其考场上灵光一现，不如提前把每种套路都练熟。
第二，背代码不如理解指针移动规则。 每道题问自己：为什么这个指针要这么移动？移动到什么条件停下？理解比记忆更可靠。
第三，408 算法题的评分是按步骤给分的。 即使写不出完整的代码，把设计思想写清楚、把关键步骤列出来，也能拿到大部分分数。千万不能空着。
双指针法是 408 数据结构性价比最高的考点之一。考频高、难度适中、套路固定。把这五道真题吃透，考场上一旦出现双指针题，就是你的送分题。
觉得有用的话，点个「在看」，转发给一起备考的研友。祝大家都能上岸理想的学校。
{embed:static}{/embed}
