C语言双指针算法详解：对撞与快慢指针实战

顾星河

发布时间：2026-10-16 | 3人浏览过

原创

C语言中的双指针算法是一种高效处理有序数组或链表的技巧。通过对撞指针和快慢指针两种策略，可以显著降低遍历过程中的时间与空间复杂度。本文将解析其核心逻辑，并通过调整数组顺序和移除元素等经典真题进行实战演示。

结果或目标

在数据结构与算法中，当面对需要成对比较、查找特定关系或重组元素的场景时，直接使用暴力嵌套循环往往导致时间复杂度过高（通常为 $O(n^2)$）。双指针算法旨在将这类问题的复杂度优化至线性级别 $O(n)$，同时利用指针操作减少额外的内存分配需求，从而在性能敏感的应用中实现更优的资源利用率。

准备条件

要有效应用双指针技术，开发者通常需要具备以下基础条件：

数据结构的有序性：对撞指针高度依赖数据的单调性或有序性；快慢指针则常用于链表结构判断。
动态内存管理意识：在C语言中，需准确理解指针与数组地址的关系，避免越界访问。
明确的状态转移条件：预先定义好两个指针的移动规则（如：左移/右移、步长差异）以及终止条件。

第1步：掌握对撞指针 (Two-End Pointers)

对撞指针适用于需要“两端向中间收敛”的场景，类似于二分查找的逻辑延伸。

入口与目的

定义指向数组最左侧的 left 指针和最右侧的 right 指针，目的是通过相向遍历缩小搜索范围或满足特定条件的子集。

动作与参数

初始化后，根据条件分别移动指针：left 向右递增，right 向左递减。当 left >= right 时结束循环。这种双向逼近能有效过滤掉不符合区间要求的元素。

可观察的完成状态

所有满足特定条件的元素被聚集到数组的一侧，或者找到了满足边界条件的最优解索引。

void hit(int *arr,int arrsize)
{
    int* left = arr;
    int* right = arr + arrsize -1;
    while(left<=right)
    {
        // 执行条件判断与移动逻辑
        left++;
        right--;
    }
}

第2步：应用快慢指针 (Fast-Slow Pointers)

快慢指针常用于涉及链表环路检测，或需要在遍历过程中压缩数据结构的场景。

入口与目的

定义两个指针 slow 和 fast，初始指向同一节点。目的是以不同的速度遍历对象，直到它们达成某种相对位置关系（如相遇、间距固定）。

动作与参数

有两种常见的启动策略：一是同步出发但步长不同；二是快指针先走若干步后再让慢指针启动。在循环体内，慢指针每次前进一步（+1），快指针前进两步（+2）或更多，具体取决于算法需求。

可观察的完成状态

对于定长删除任务，快指针遍历完毕且慢指针停在新逻辑数组的有效末尾；对于环路检测，两指针在非NULL节点相遇。

// 模拟同步走法的核心逻辑
void speed(int *arr)
{
   int* fast = arr;
   int* slow = arr;
   while(slow<fast)
   {
      // 条件判断
      slow++; 
      // 非无条件时 fast++
   }
}

第3步：真题实战——调整数组顺序使奇数位于偶数前面

这是一个典型的对撞指针应用场景。目标是保持奇数的相对顺序并不重要（若要求稳定排序则需其他方案），仅要求奇数在前，偶数在后。

操作步骤

定义左右指针 left 指向起始，right 指向末尾。
左指针跳过已存在的奇数，直到遇到偶数停止。
右指针跳过已存在的前置偶数，直到遇到奇数停止。
若 left < right，交换两者值，并向内收缩。

int* reOrderArray(int* array, int arrayLen, int* returnSize ) {
    *returnSize = arrayLen;
    int* left = array;
	int* right = array + arrayLen - 1;
	while (left < right)//(1) 控制遍历范围
	{
		while (left < right && *left % 2 == 1)//(2) 找左边第一个偶数
			left++;
		while (left < right && *right % 2 == 0)//(3) 找右边第一个奇数
			right--;
		if (left < right)//(4) 防止重复交换
		{
			int tmp = *left;
			*left = *right;
			*right = tmp;
		}
		left++;
		right--;
	}
	return array;
}

该方法通过左右路程各半的遍历，仅需一次交换即可完成重排，时间复杂度为 $O(n)$。

第4步：真题实战——LeetCode 移除元素 (Remove Element)

此题适合使用快慢指针思想。无需真实释放内存或物理删除，只需覆盖无效元素并返回新长度。

操作步骤

设定慢指针 p2 作为“写指针”，快指针 p1 作为“读指针”。
遍历整个数组，若当前值 *p1 != val，则将该值复制到 *p2，并推进 p2。
无论是否复制，快指针 p1 始终向前。
最终 p2 的位置即为不包含目标值的新数组长度。

int removeElement(int* nums, int numsSize, int val) {
	int* p1 = nums;
	int* p2 = nums;
	int sz = numsSize;
	for (; p1 < nums + numsSize; p1++)
	{
		if (*p1 != val)
		{
			*p2 = *p1;
			*p2++;
		}
		else
			sz--;
	}
	return sz;
}

该实现将原本需要多次移位操作的 $O(n^2)$ 复杂度降为了 $O(n)$ 的单次扫描。