双指针问题 | YOLOのBLOG

前言

双指针具体就是用两个变量动态存储两个结点，来方便我们进行一些操作。通常用在线性的数据结构中。
特别是链表类的题目，经常需要用到两个或多个指针配合来记忆链表上的节点，完成某些操作。

一、合并两个有序数组（简）

题目

给你两个按非递减顺序排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。
请你合并 nums2 到 nums1 中，使合并后的数组同样按非递减顺序排列。
注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

示例 1：
输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]
解释：需要合并 [1,2,3] 和 [2,5,6] 。
合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。

示例 2：
输入：nums1 = [1], m = 1, nums2 = [], n = 0
输出：[1]
解释：需要合并 [1] 和 [] 。
合并结果是 [1] 。

示例 3：
输入：nums1 = [0], m = 0, nums2 = [1], n = 1
输出：[1]
解释：需要合并的数组是 [] 和 [1] 。
合并结果是 [1] 。
注意，因为 m = 0 ，所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。

提示：
nums1.length == m + n
nums2.length == n
0 <= m, n <= 200
1 <= m + n <= 200
-10^9 <= nums1[i], nums2[j] <= 10^9

题解1

首先我们可以用双指针+额外存储空间来实现O(m + n)的时间复杂度。
因为原有数组已经是从小到大排好序了，所以直接从后往前遍历。

class Solution {
 public:
  void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
    int p1 = m - 1, p2 = n - 1; // 双指针
    int sorted[m + n];  // 额外存储空间
    int cur;
    while (p1 >= 0 || p2 >= 0) {
      if (p1 == -1) {
        // p1遍历到头时,记录nums2[p2]的值
        cur = nums2[p2];
        p2--;
      } else if (p2 == -1) {
        // p2遍历到头时,记录nums1[p1]的值
        cur = nums1[p1];
        p1--;
      } else if (nums1[p1] > nums2[p2]) {
        // nums1[p1]>nums2[p2]时,记录nums1[p1]的值
        cur = nums1[p1];
        p1--;
      } else {
        // nums1[p1]<=nums2[p2]时,记录nums2[p2]的值
        cur = nums2[p2];
        p2--;
      }
      // 向后更新sorted
      sorted[p1 + p2 + 2] = cur;  // 从最后一个开始,m+n=p1+p2+2
    }
    for (int i = 0; i < m + n; ++i) {
      nums1[i] = sorted[i];
    }
  }
};

题解2

首先题目里告诉了我们nums1.length >= m+n，所以我们可以直接原地修改，把nums2放入nums1中，将空间复杂度降低到O(1)。
建立三个指针，两个指针用于指向nums1和nums2的初始化元素数量的末位，也就是分别指向m-1和n-1的位置（设为p1，p2），还有一个指针，我们指向nums1数组m+n-1的位置即可（设为tail）。
其余的跟上面一样

class Solution {
 public:
  void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
    int p1 = m - 1, p2 = n - 1;
    int tail = m + n - 1;
    int cur = 0;
    while (p1 >= 0 || p2 >= 0) {
      if (p1 == -1) {
        // p1遍历到头时,记录nums2[p2]的值
        cur = nums2[p2];
        p2--;
      } else if (p2 == -1) {
        // p2遍历到头时,记录nums1[p1]的值
        cur = nums1[p1];
        p1--;
      } else if (nums1[p1] > nums2[p2]) {
        // nums1[p1]>nums2[p2]时,记录nums1[p1]的值
        cur = nums1[p1];
        p1--;
      } else {
        // nums1[p1]<=nums2[p2]时,记录nums2[p2]的值
        cur = nums2[p2];
        p2--;
      }
      // 向后更新nums1
      nums1[tail] = cur;
      tail--;
    }
  }
};

二、字符串相加（简）

题目

给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和并同样以字符串形式返回。
你不能使用任何內建的用于处理大整数的库（比如 BigInteger），也不能直接将输入的字符串转换为整数形式。

示例 1：
输入：num1 = “11”, num2 = “123”
输出：”134”

示例 2：
输入：num1 = “456”, num2 = “77”
输出：”533”

示例 3：
输入：num1 = “0”, num2 = “0”
输出：”0”

提示：
1 <= num1.length, num2.length <= $10^4$
num1 和num2 都只包含数字 0-9
num1 和num2 都不包含任何前导零

题解

可以使用双指针来模拟人工计算，步骤如下：
1、创建指针p1指向num1末位数字，p2指向num2末位数字。
2、p1、p2数字相加，进位就用add来记录进位值，无则为0。
3、若产生进位，则当前数字为(p1+p2)%10的值。
4、若遍历过程中，num1或num2当前已无数字，则用0补位来计算。

class Solution {
 public:
  string addStrings(string num1, string num2) {
    int p1 = num1.length() - 1, p2 = num2.length() - 1, add = 0;
    string nums = "";
    while (p1 >= 0 || j >= 0 || add != 0) {
      int x = p1 < 0 ? 0 : num1[p1] - '0';
      int y = p2 < 0 ? 0 : num2[p2] - '0';
      int res = x + y + add;
      nums.push_back(res % 10);
      add = res / 10;
      p1--;
      p2--;
    }
    return nums;
  }
};

三、删除链表的倒数第N个结点（中）

题目

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

示例 1：

graph LR
    1 --> 2
    2 --> 3
    3 --> 4
    4 --> 5

—>

graph LR
    1 --> 2
    2 --> 3
    3 --> 5

输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

示例 2：
输入：head = [1], n = 1
输出：[]

示例 3：
输入：head = [1,2], n = 1
输出：[1]

提示：
链表中结点的数目为 sz
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz

题解

很简单，可以设想双指针slow和fast，fast先移动，使其和slow间隔n；
然后两者同时移动，当fast指向末尾的NULL时，那么slow->next就是要删除的节点。
这里有个问题是，我要删除的节点是头节点怎么办，那此时fast移动间隔n后，肯定是指向NULL，所以直接加个判断就能解决。

class Solution {
 public:
  ListNode* removeNthFromEnd(ListNode* head, int n) {
    ListNode* slow = head;
    ListNode* fast = head;
    for (int i = 0; i < n; i++) {
      fast = fast->next;
    }
    if (fast == NULL) {
    // 判断要删除的节点是头节点
      return head->next;
    }
    while (fast->next) {
      slow = slow->next;
      fast = fast->next;
    }
    slow->next = slow->next->next;
    return head;
  }
};