C程序 双指针技术使用攻略

双指针技术（Two Pointers）是一种常见的算法思想，在C程序中也有广泛的应用场景。其核心思想是使用两个指针扫描数组，并找到特定的数据。

双指针技术原理

双指针技术涉及到两个指针，一个指向数组的起始位置，另一个指向数组的结束位置。双指针可向数组中心移动，并在数组中查找特定数据或执行其他操作。双指针技术可以大大减少时间复杂度。

双指针应用示例1：数组的旋转

问题描述：给定一个有n个元素的数组，将数组向右旋转k步。其中n > 0, k > 0。

示例输入：

nums: [1,2,3,4,5,6,7], k: 3

示例输出：

[5,6,7,1,2,3,4]

解题思路：

首先将数组反转。

然后，将前面k个元素再次进行反转。

最后，将后面的n-k个元素进行反转。

在上述示例中，数组为[1,2,3,4,5,6,7]，k=3。

1. 反转整个数组：[7,6,5,4,3,2,1]
2. 反转前k个元素：[5,6,7,4,3,2,1]
3. 反转后n-k个元素：[5,6,7,1,2,3,4]

这种方法的时间复杂度为O(n)。

代码示例：

void reverse(int* nums, int i, int j) {
    int temp;
    while (i < j) {
        temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
        i++;
        j--;
    }
}

void rotate(int* nums, int numsSize, int k) {
    k %= numsSize;
    reverse(nums, 0, numsSize-1);
    reverse(nums, 0, k-1);
    reverse(nums, k, numsSize-1);
}

双指针应用示例2：链表中倒数第k个节点

问题描述：给定一个链表，返回该链表中倒数第k个节点，其中k > 0。

示例输入：

head: [1,2,3,4,5], k: 2

示例输出：

4

解题思路：

使用双指针法，两个指针之间的偏差为k。

1. 首先将快指针移到链表的第k个节点，慢指针指向链表的第一个节点。
2. 然后慢指针和快指针一起向前移动，直到快指针到达链表的尾部。
3. 慢指针就指向了链表中倒数第k个节点。

代码示例：

struct ListNode* getKthFromEnd(struct ListNode* head, int k){
    struct ListNode* fast = head;
    struct ListNode* slow = head;
    for(int i = 0; i < k; i++) {
        fast = fast->next;
    }
    while(fast) {
        fast = fast->next;
        slow = slow->next;
    }
    return slow;
}

双指针技术的其他应用场景

除了上面的两个示例之外，双指针技术还可以用于以下场景：

• 判断一个链表是否有环
• 找到链表中的中间节点
• 在有序数组中找到两个数，使它们的和等于给定的数

等等。

总的来说，双指针技术是一种简单且高效的算法，可以大大提高算法执行的效率。