少儿编程C++基础：双指针总结（一）-成都凡恩机器人联盟

双指针是一种解决问题的技巧或者思维方式，指在访问一个序列中的数据时使用两个指针进行扫描，两个指针可以是同向的，也可以是反向的；我们的关注点可以是这两个指针指向的两个元素本身，也可以是两个指针中间的区域。

快慢指针

01、快慢指针的概念
快慢指针是两个指针同向移动，某一时刻来看两个指针一个在前，一个在后，即快指针和慢指针。造成两个指针一前一后的原因有两种情况：

①．两个指针速度相同，但是出发时间不同，也可以认为是出发起始位置不同，在两个指针都出发后会以固定的距离间隔一前一后的向前移动；

②．两个指针速度不同，但是从同一个起点同时出发，之后会以固定的速度差一前一后的向前移动，两个指针的距离间隔随时间规律的递增；

02、应用示例-链表中倒数第k个节点

输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。例如，一个链表有6个节点，从头节点开始，它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个节点是值为4的节点。示例：给定一个链表:
1->2->3->4->5, 和 k = 2. 返回链表 4->5.

力扣（LeetCode）面试题22

访问链表的节点只能从前往后进行节点的遍历。对应本题一般解法可以先从头到尾进行一趟遍历得到链表长度 length ,然后再从头开始进行一趟 遍历，但是只遍历
length – k 个节点即可。

利用双指针可以只进行一次遍历即可，两个指针都从头节点出发，让快指针先走 k 步，然后慢指针再出发，两个指针以相同的速度前进，则两个 指针间的距离始终为 k
,所以当快指针刚好走过链接尾节点时，慢指针刚好到达倒数第 k 个节点的位置。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* getKthFromEnd(ListNode* head, int k) {
        ListNode *fast = head, *slow = head; //初始化
        while(k--) {   //让false指针先走K步
            fast = fast->next;
        }
        while(fast != nullptr) {//两个指针以相同的步长同时移动，直到 fast == nullptr
            fast = fast->next;
            slow = slow->next;
        }
        return slow;//slow刚好为倒数第k的位置
    }
};

03、应用示例-链表的中间结点

给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。示例 1：输入：[1,2,3,4,5]
输出：此列表中的结点 3 (序列化形式：[3,4,5]) 返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。注意，我们返回了一个
ListNode 类型的对象 ans，这样：ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及
ans.next.next.next = NULL

力扣（LeetCode）第876题

访问链表的节点只能从前往后进行节点的遍历。对应本题一般解法可以先从头到尾进行一趟遍历得到链表长度 length ,然后再从头开始进行一趟 遍历，遍历到第
N/2 个元素即可。

同样，利用双指针可以只进行一次遍历即可，两个指针同时从头节点结点出发，快指针每次走两步，慢指针走一步，则相同的时间内快指针前进
的距离始终是慢指针的两倍，所以当快指针刚好走过链接尾结点时，慢指针刚好到达链表的中间结点位置。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        ListNode * fast= head, * slow = head;//初始化
        while(fast != NULL && fast->next !=NULL)
        {
            slow = slow->next;//慢指针走一步
            fast = fast->next;//快指针走两步
            fast = fast->next;
            
        }
        return slow;
    }
};

04、应用示例-环形链表

给定一个链表，判断链表中是否有环。为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是
-1，则在该链表中没有环。示例 1：输入：head = [3,2,0,-4], pos = 1 输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

力扣（LeetCode）第141题

我们对链表从头结点开始进行遍历，若链表中存在环，则环内的结点会重复一直遍历，不存在环或者环外的结点只会遍历一次；因此我们用一个 set
来存储已经遍历过的结点，当遍历到一个结点时查找 set中是否存在，若已经存在则一定存在环。

也可以使用双指针来解答本题，两个指针同时从头节点结点出发，快指针每次走两步，慢指针走一步，则单位时间内快指针相对慢指针移动距离的增量为 1
，即经过相同的时间 k ,快指针比慢指针多走了 k
步；当两个指针都进入环中时，假设规定慢指针在前、快指针在后，即快指针追赶慢指针，因为单位时间内快指针可以把距离缩短 1
步，因此随着时间的推移快指针肯定会追赶上慢指针。若不存在环，则快指针和慢指针不会在链表中的某个结点相遇。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
       ListNode * fast= head,* slow = head;//初始化
       while(fast != NULL && fast->next !=NULL)
       {
            slow = slow->next;//慢指针走一步
            fast = fast->next;//快指针走两步
            fast = fast->next;
            if( fast == slow )//两者相遇则有环
                return true;   
       }
       return false;
    }
};