快慢指针是指针的一种类型，在这里我们来了解下快慢指针

让我们来看一道题

一、题目

876. 链表的中间结点

首先我们对这道题进行分析，最容易让人想到的方法是直接使用n/2找到中点，如果我们不对链表进行遍历，我们该怎么做呢？

我们可以使用快慢指针来解决这道题。

二、思路

1. 我们使用slow和fast分别指向head
2. slow和fast同时移动，slow每次移动一个位置 ，fast每次移动两个位置。
3. 当fast移动到null时，slow处于链表中点。

三、代码

ListNode middleNode(ListNode head) {// 快慢指针初始化指向 headListNode slow = head, fast = head;// 快指针⾛到末尾时停⽌while (fast != null && fast.next != null) {// 慢指针⾛⼀步，快指针⾛两步slow = slow.next;fast = fast.next.next;}// 慢指针指向中点return slow;
}

JS实现

/*** Definition for singly-linked list.* function ListNode(val, next) {*     this.val = (val===undefined ? 0 : val)*     this.next = (next===undefined ? null : next)* }*/
/*** @param {ListNode} head* @return {ListNode}*/
var middleNode = function(head) {// if(!head.next) return head;let slow = head;let fast = head;while(fast != null && fast.next != null) {fast = fast.next.next;slow = slow.next;}return slow;
};

我们还可以使用快慢指针来判断链表是否包含环

一、解决思路

利用快慢指针的特性，如果有环，那么一定会出现fast==slow的情况

二、代码

boolean hasCycle(ListNode head) {// 快慢指针初始化指向 headListNode slow = head, fast = head;// 快指针⾛到末尾时停⽌while (fast != null && fast.next != null) {// 慢指针⾛⼀步，快指针⾛两步slow = slow.next;fast = fast.next.next;// 快慢指针相遇，说明含有环if (slow == fast) {return true;}}// 不包含环return false; }

如果有环的话，我们如何求这个环的起点呢？

一、解决思路

1. 设快慢指针相遇时，slow走了k，fast走了2k
2. k一定是环的整数倍
3. 设slow与fast相遇时，此处距离起点的距离为m
4. 那么k-m为head距离环起点的距离
5. 因为k是环的整数倍，那么相遇的位置再走k-m也一定能到环的起点
6. 这时，我们将slow指向head（fast指向head也行）
7. 将slow和fast的速度调为一样
8. 当它们在此相遇的时候，这个位置就是环的起点。

二、代码实现

ListNode detectCycle(ListNode head) {ListNode fast, slow;fast = slow = head;while (fast != null && fast.next != null) {fast = fast.next.next;slow = slow.next;if (fast == slow) break;}// 上⾯的代码类似 hasCycle 函数if (fast == null || fast.next == null) {// fast 遇到空指针说明没有环return null;}// 重新指向头结点slow = head;// 快慢指针同步前进，相交点就是环起点while (slow != fast) {fast = fast.next;slow = slow.next;}return slow;
}

---

剑指 Offer 52. 两个链表的第一个公共节点

一、分析

1. 因为给的两条链表可能长度不一样，所以我们可以将两条链表放到一起
   
   
2. 如果两条链表没有相交的结点，那么能否正确的返回null呢？上述解法包括了这种情况，当比较到最后一个结点时，两条链表此时的结点都为null，两节点相同并返回null

二、代码

/*** Definition for singly-linked list.* function ListNode(val) {*     this.val = val;*     this.next = null;* }*//*** @param {ListNode} headA* @param {ListNode} headB* @return {ListNode}*/
var getIntersectionNode = function(headA, headB) {let p1 = headA, p2 = headB;while(p1!=p2) {if(p1!=null) {p1 = p1.next;} else {p1 = headB;}if(p2!=null) {p2 = p2.next;} else {p2 = headA;}}return p1;
};

上述算法题解参考labuladong的算法秘籍