双指针

• 双指针
  • 1. 介绍
  • 2. 分类
    • 2.1. 对撞指针
    • 2.2. 快慢指针
  • 3. 示例
    • 3.1. 对撞指针
    • 3.2. 快慢指针

该文记录双指针的主要思想。

双指针

1. 介绍

双指针指的是在遍历对象的过程中，不是普通的使用单个指针进行访问，而是使用两个相同方向（快慢指针）或者相反方向（对撞指针）的指针进行扫描，从而达到相应的目的。

2. 分类

2.1. 对撞指针

对撞指针（首尾指针、左右指针），是指在有序数组中将指向最左侧的索引定义为左指针(left)，最右侧的定义为右指针(right)，然后从两头向中间进行数组遍历。对撞数组适用于有序数组，也就是说当你遇到题目给定有序数组时，应该第一时间想到用对撞指针解题。

2.2. 快慢指针

两个指针从同一侧开始遍历数组，将这两个指针分别定义为快指针（fast）和慢指针（slow），两个指针以不同的策略移动，直到两个指针的值相等（或其他特殊条件）为止，如fast每次增长两个，slow每次增长一个。

3. 示例

3.1. 对撞指针

// 翻转字符串
void reverseString(vector<char>& s) 
{
    int left  = 0;
    int right = s.size() - 1;
    while (left < right) 
    {
        swap(s[left], s[right]);
        ++left;
        --right;
    }
}

344. 反转字符串

3.2. 快慢指针

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
// 获取链表中间节点
ListNode * middleNode(ListNode * head)
{
    ListNode * slow = head;
    ListNode * fast = head;
    while (fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

141. 环形链表

876. 链表的中间结点