双指针问题分类：

1.快慢指针（追及指针）

常见于链表

  • 判断链表是否有环
  • 判断链表是否有环，且找出入环点
  • 快慢指针找中点
  • 奇数个节点的话，slow在正中；偶数个节点的话，slow在正中偏左（前半部分链表的末尾处，方便分割前后两部分链表）
	Listnode* slow = head;
	// 经验所得，fast设置成这样比较方便slow的定位
	// 如果fast = head的话，临界状态下slow指向的是后半部分子链表的头部，不方便前后子链表分割
	Listnode* fast = head->next;
	while(fast && fast->next){
      fast = fast->next->next;
      slow = slow->next;
    }

  • eg偶数长度:

    3 2 4 6 5 1 7 8

轮次 名称 位置(所指向元素）
1 slow 3
1 fast 2
2 slow 2
2 fast 6
3 slow 4
3 fast 1
4 slow 6
4 fast 8(此时已不满足fast && fast->next）

  • eg奇数长度:

    3 2 4 6 5 1 7

轮次 名称 位置(所指向元素）
1 slow 3
1 fast 2
2 slow 2
2 fast 6
3 slow 4
3 fast 1
4 slow 6
4 fast nullptr(此时已不满足fast && fast->next）

2.碰撞指针

常见于数组

  • 判断回文
  • 接雨水

3.平行指针

常见多个数组或链表同时出现

  • 合并升序数组A和B到A中
  • 判断链表是否相交
  • 合并两个有序链表
  • 对无序链表进行排序（快慢指针分半，平型指针进行合并）