Ciallo～(∠・ω< )链表中双指针的相对性
前言
双指针技巧在链表中非常常见，笔者刷了一天leetcode上这类题目，个人认为，掌握双指针的要点在于对相对位置的把控，下面通过一些题目来说明。
链表的中间节点
先来看leetcode的第876题链表的中间节点
给定一个头结点为 head 的非空单链表，返回链表 的中间节点。如果有两个中间节点，则返回第二个中间节点。
示例 1：输入：head = [1,2,3,4,5] 输出：[3,4,5] 解释：链表只有一个中间节点，值为 3 。示例 2：
输入：head = [1,2,3,4,5,6] 输出：[4,5,6] 解释：链表有两个中间节点，值分别为 3 和 4 ，返回第二个中间节点。
一般来说，我们会先遍历一遍链表，计算出链表的长度len，然后再遍历一遍，找到第len/2+1个节点。
但是这需要两次遍历，是否有更加高效的办法呢？
这时候，就需要我们巧妙的设置双指针的相对位置了，这个相对位置为我们提供了额外的信息——这种信息也许本需要额外一次遍历。
那么如何设置相对位置呢？
- 这种相对可以是锁死的距离，比如说leetcode的第19题中，我们需要删除倒数第n个节点，我们可以设置两个指针
fast和slow，让fast先走n步，然后slow和fast一起走，当fast走到链表末尾时，slow正好走到倒数第n个节点。 - 也可以设置不同的遍历速度，比如说本题，我们可以设置
fast每次走两步，slow每次走一步，当fast走到链表末尾时，slow正好走到中间节点。 代码实现如下：
class Solution {
public:
ListNode* middleNode(ListNode* head) {
ListNode* fast = head;
ListNode* slow = head;
int cnt = 0;
while (fast != nullptr) {
fast = fast->next;
cnt++;
if (cnt % 2 == 0) {
slow = slow->next;
}
}
return slow;
}
};备注：关于
fast和slow指针的写法，上述代码采用了如下方式：fast = fast->next; cnt++; if (cnt % 2 == 0) { slow = slow->next; }也可以简化为：
while (fast != nullptr && fast->next != nullptr) { fast = fast->next->next; slow = slow->next; }这种写法可以有效避免 undefined behavior，更加安全和简洁。
举一反三，下次题目找1/3处节点，fast每次走三步，slow每次走一步即可，以此类推。
环形链表判断
先来看leetcode的第141题环形链表
给你一个链表的头节点 head ，判断链表中是否有环。 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。 如果链表中存在环，则返回 true 。 否则，返回 false 。
示例 1：输入：head = [3,2,0,-4], pos = 1 输出：true 解释：链表中有一个环，其尾部连接到第二个节点。示例 2：
输入：head = [1,2], pos = 0 输出：true 解释：链表中有一个环，其尾部连接到第一个节点。示例 3：
输入：head = [1], pos = -1 输出：false 解释：链表中没有环。
是否有环的标志在于，指针到最后是否走到nullptr
我们可以使用和上题类似的思路，设置两个指针fast和slow，fast每次走两步，slow每次走一步，如果链表中有环，那么fast和slow最终会相遇，如果没有环，fast会走到链表末尾。
代码实现如下：
class Solution {
public:
bool hasCycle(ListNode* head) {
ListNode* fast = head;
ListNode* slow = head;
while (fast != nullptr && fast->next != nullptr) //这里注意条件顺序
{
fast = fast->next->next;
slow = slow->next;
if (fast == slow) {
return true;
}
}
return false;
}
};当然，通过hashset等数据结构也可以实现，但是空间复杂度为O(n)，而双指针的空间复杂度为O(1)，显然双指针要更加轻巧。 同样写一则hashset作为参考：
class Solution {
public:
bool hasCycle(ListNode* head) {
unordered_set<ListNode*> nodesSeen;
while (head != nullptr) {
if (nodesSeen.find(head) != nodesSeen.end()) {
return true;
}
nodesSeen.insert(head);
head = head->next;
}
return false;
}
};环的起点
先来看leetcode的第142题环形链表 II 这一次，我们不仅要判断链表中是否有环，还要找到环的起点。 这似乎很困难，因为我们可以先判断环是否存在，但是我们不知道指针是在哪里相遇的——你可以想象环是一个滚筒洗衣机，指针可能在里面转无数圈才遇上() 或许，先用hashset？
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
unordered_set<ListNode*> nodesSeen;
while (head != nullptr) {
if (nodesSeen.find(head) != nodesSeen.end()) {
return head;
}
nodesSeen.insert(head);
head = head->next;
}
return nullptr;
}
};等一下，我们一直在纠结指针在环上的具体位置，但是双指针的妙处在于，提供信息的是指针相对的运动！
我们假设head到环起点的距离为a，环起点到相遇点的距离为b，相遇点到环起点的距离为c，则有如下关系：
fast走的路程为a + n1*(b+c) + bslow走的路程为a + n2*(b+c) + b- 其中
n1和n2为fast和slow在环上转的圈数 - 由于
fast的速度是slow的两倍，所以有2*(a + n2*(b+c) + b) = a + n1*(b+c) + b - 化简可得
a = (n1 - 2*n2 - 1)*(b+c) + c - 也就是说，从
head到环起点的距离a，等于从相遇点到环起点的距离c，加上若干个环的周长(b+c) - 因此，我们可以设置两个指针，一个从
head出发，一个从相遇点出发，每次都走一步，在相遇点的指针到达起点后，它就可以视作“等待”起点指针走完(n1-2*n2-1)个周期c，当它们相遇时，就是环的起点。 - 代码实现如下：
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
ListNode* fast = head;
ListNode* slow = head;
bool hasCycle = false;
while (fast != nullptr && fast->next != nullptr) {
fast = fast->next->next;
slow = slow->next;
if (fast == slow) {
hasCycle = true;
break;
}
}
if (!hasCycle) {
return nullptr;
}
ListNode* ptr1 = head;
ListNode* ptr2 = slow;
while (ptr1 != ptr2) {
ptr1 = ptr1->next;
ptr2 = ptr2->next;
}
return ptr1;
}
};总结
通过以上三道题，我们可以看到，双指针的妙处在于，提供信息的是指针相对的运动，而不是指针的具体位置。
- 这种相对可以是锁死的距离，比如说删除倒数第n个节点时，
fast和slow相距n个节点 - 也可以是不同的遍历速度，比如说找中间节点时，
fast每次走两步，slow每次走一步 - 还可以是相遇后，重新设置指针，从
head和相遇点出发，每次走一步，最终在环起点相遇