[算法]双指针的种种应用

本文使用C语言

Q:为什么要用双指针?

A:因为
通过使用双指针可以使算法的时间复杂度降低(或者降低遍历次数),有时也能降低空间复杂度

分类

根据双指针的用法，可分为前后双指针,头尾双指针,快慢双指针.....

前后双指针

应用一 删除排序数组中的重复项

要求:原地删除,并返回新数组的长度，不需要考虑数组中超出新长度后面的元素。

思路:通过创建一前一后两个指针，前指针指向上一个元素，后指针向后历遍,一旦找到不同的元素,前指针指向下一个位置，并视为空位，通过后指针找到目标元素,并存入前指针目前所指向的空位。然后后指针接着遍历，直至遍历整个数组.

//代码实现
int removeDuplicates(int* nums, int numsSize){
    int* left = nums;
    int*right = nums+1;
    int ret = 1;
    //遍历数组
    for (int i=0;i<numsSize-1;i++)
    {
        if(*left != *right)
        {
            left++;
            *left = *right;
            right++;
            ret++;
        }
        else
        {
            right++;
        }
    }
    return ret;
}

分析:这个函数只遍历的一遍数组，没有复制数组,所以时间复杂度为O(n),空间复杂度为O(1);

头尾双指针

应用一 翻转数组/字符串

关于翻转，首先想到的应该是创建一个等长的空数组，再同时顺序遍历原数组和逆序遍历空数组，逐位储存到空数组，然后再同时顺序遍历两个数组，将已逆序的数组拷贝至原数组

缺点：需要多次遍历，且空间复杂度为O(n)

使用双指针优化：整个数组的翻转可逐步拆解为：第一个和最后一个互换、第二个和倒数第二个互换、、、第N个数和倒数第N个数互换，直至中间。此处便可使用双指针，头尾指针各自一边交换所指向的内容，一边向中间靠近

//代码实现-这里是翻转字符串
void reverseString(char* s, int sSize){
    int *left = s;//头指针
    int *right = s + sSize-1;//尾指针
    while(left<right)//尚未到达中间时
    {
        char tmp = *left;
        *left = *right;
        *right = tmp;
        left++;
        right--;
    }
}

快慢双指针

应用一 删除链表倒数第K个节点

一般解法：先遍历一遍链表获得链表总数N,再二次遍历到N-K处的节点，并执行删除

如何优化：使用快慢双指针，仅需遍历一次，就能用慢指针定位目标节点

//代码实现
struct ListNode* removeNthFromEnd(struct ListNode* head, int n){
    //创建哨兵位解决头删问题
    struct ListNode* dummy = (struct ListNode*)malloc(sizeof(struct ListNode));
    dummy->val = 0;
    dummy->next = head;

    struct ListNode* slow = dummy;
    struct ListNode* fast = dummy;
    while (int i = 0;i<n+1;n++)//移动fast
    {
        fast = fast->next;
    }
    
    while(fast != NULL)//同时遍历
    {
        fast= fast->next;
        slow= slow->next;
    }
    //此时slow指向目标节点的前一个节点
    struct ListNode* tmp = slow->next;
    slow->next = slow->next->next;
    free(tmp);
    return dummy->next;
}

应用二 找出并返回链表中间的节点

注:偶数个节点时删除前一个中间节点

一般解法：依然是先遍历一遍链表，然后定位中间的节点,二次遍历

如何优化：使用慢指针(一步走一个节点)和快指针(一步走两个节点)，二者同时遍历，直至快指针指向NULL或快指针指向尾节点

当遍历结束时，慢指针指向目标中间节点

//代码实现
struct ListNode* middleNode(struct ListNode* head){
    struct ListNode *slow = head;
    struct ListNode *fast = head;
    while(fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next; 
    }

    return slow;
}