面试的时候经常碰见诸如获取倒数第k个元素，获取中间位置的元素，判断链表是否存在环，判断环的长度等和长度与位置有关的问题。这些问题都可以通过灵活运用双指针来解决。
问题一:剑指Offer.链表中倒数第k个节点问题描述:
输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。
例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。
思路解读：设有两个指针 p 和 q，初始时均指向头结点。首先，先让 p 沿着 next 移动 k 次。此时，p 指向第 k+1个结点，q 指向头节点，两个指针的距离为 k 。然后，同时移动 p 和 q，直到 p 指向空，此时 q 即指向倒数第 k 个结点。可以参考下图来理解：
代码示例:
class Solution {
public:
ListNode* getKthFromEnd(ListNode* head, int k) {
ListNode *p = head, *q = head; //初始化
while(k--) { //将 p指针移动 k 次
p = p->next;
}
while(p != nullptr) {//同时移动，直到 p == nullptr
p = p->next;
q = q->next;
}
return q;
}
};
问题二:LeetCode.链表的中间节点
问题描述:
给定一个头结点为 head 的非空单链表，返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点。
思路解读：设有两个指针 fast 和 slow，初始时指向头节点。每次移动时，fast向后走两次，slow向后走一次，直到 fast 无法向后走两次。这使得在每轮移动之后。fast 和 slow 的距离就会增加一。设链表有 n 个元素，那么最多移动 n/2 轮。当 n 为奇数时，slow 恰好指向中间结点，当 n 为 偶数时，slow 恰好指向中间两个结点的靠前一个(可以考虑下如何使其指向后一个结点呢）(只需要加判断fast的下一个不为空，即不清楚能否走两次只要下一个位置不空，就往下走，直到遇到空走不了为止)
下述代码实现了慢指针指向靠后结点,即题目要求
代码示例:
class Solution {
public:
ListNode* middleNode(ListNode* head) {
//快慢指针
ListNode *fast=head;
ListNode *slow=head;
//快的一次走两下，直到一次走不了两次
while(fast!=nullptr&&fast->next!=nullptr)
{
slow=slow->next;
fast=fast->next->next;
}
return slow;
}
};
问题三:LeetCode.环形链表
首先明白是否存在环的问题。如果将尾结点的 next 指针指向其他任意一个结点，那么链表就存在了一个环。
问题描述:
给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ，则返回 true 。 否则，返回 false
思路解读:
当一个链表有环时，快慢指针都会陷入环中进行无限次移动，然后变成了追及问题。想象一下在操场跑步的场景，只要一直跑下去，快的总会追上慢的。当两个指针都进入环后，每轮移动使得慢指针到快指针的距离增加一，同时快指针到慢指针的距离也减少一，只要一直移动下去，快指针总会追上慢指针。
具体地，我们定义两个指针，一快一满。慢指针每次只移动一步，而快指针每次移动两步。初始时，慢指针在位置 head，而快指针在位置 head.next。这样一来，如果在移动的过程中，快指针反过来追上慢指针，就说明该链表为环形链表。否则快指针将到达链表尾部，该链表不为环形链表。
代码示例:
class Solution {
public:
bool hasCycle(ListNode *head) {
//快慢指针
if(head==nullptr||head->next==nullptr)
return false;
ListNode* fast=head->next;
ListNode* slow=head;
while(slow!=fast)
{
if(fast==nullptr||fast->next==nullptr)
return false;
else
slow=slow->next; //慢的走一步
fast=fast->next->next; //快的走两步
}
return true;
}
};
最后一个问题，如果存在环，如何判断环的长度呢？方法是，快慢指针相遇后继续移动，直到第二次相遇。两次相遇间的移动次数即为环的长度。
问题四:LeetCode.相交链表问题描述:
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null
思路解读：设「第一个公共节点」为 node ，「链表 headA」的节点数量为 a ，「链表 headB」的节点数量为 b ，「两链表的公共尾部」的节点数量为 c ，则有：
头节点 headA 到 node 前，共有 a - c 个节点；
头节点 headB 到 node 前，共有 b - c个节点；
考虑构建两个节点指针 A , B 分别指向两链表头节点 headA , headB ，做如下操作：
指针 A 先遍历完链表 headA ，再开始遍历链表 headB ，当走到 node 时，共走步数为：
a + (b - c)
指针 B 先遍历完链表 headB ，再开始遍历链表 headA ，当走到 node 时，共走步数为：
b + (a - c)
如下式所示，此时指针 A , B 重合，并有两种情况：
a + (b - c) = b + (a - c)
若两链表 有 公共尾部 (即 c > 0 ) ：指针 A , B 同时指向「第一个公共节点」node 。
若两链表 无 公共尾部 (即 c = 0 ) ：指针 A , B 同时指向 null 。
代码示例:
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
if(headA==nullptr||headB==nullptr)
{
return nullptr;
}
//双指针
ListNode *pa=headA;
ListNode *pb=headB;
while(pa!=pb)
{
pa=pa==nullptr?headB:pa->next;
pb=pb==nullptr?headA:pb->next;
}
return pa;
}
};
如果觉得文章写得还不错，麻烦点个赞支持一下，欢迎评论，互相学习！
