本系列是算法通关手册LeeCode的学习笔记
算法通关手册（LeetCode） | 算法通关手册（LeetCode） (itcharge.cn)
本系列为自用笔记，如有版权问题，请私聊我删除。
目录
一，双指针简介（Two Pointers）
二，起点不一致的快慢指针
三，步长不一致的快慢指针
判断链表中是否含有环：
四，分离双指针
一，双指针简介（Two Pointers）
在遍历元素的过程中，使用两个指针进行访问，并通过两个指针的位置与移动的条件，达到解决问题的目的。
双指针有快慢指针与分离双指针，在链表中时常有环结构，因此方向不同的对撞双指针很少使用，且不够方便。
二，起点不一致的快慢指针
两个指针从同一侧开始遍历链表，但是两个指针的起点不一样。快指针比慢指针先走 n 步，直到快指针移动到链表尾端为止。
伪代码模板：
slow = head
fast = head
while n:
fast = fast.next
n -= 1
while fast:
fast = fast.next
slow = slow.next
例题：
19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode）
找到倒数第 n 个指针，然后删除；
即找到某节点 p，p 到链表尾部还有 n 个节点；
可是使用快慢指针，fast 先走 n 个节点，使fast 领先 slow 指针 n 个节点；
当 fast 走到链表尾部是， slow 指向将要移除的节点。
令 slow 开始位置为 head 的前一个节点，则退出循环时，slow 指向移除节点的前一个节点。
class Solution:
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
dummy = ListNode()
dummy.next = head
fast = head
while n:
fast = fast.next
n -= 1
slow = dummy
while fast:
fast = fast.next
slow = slow.next
slow.next = slow.next.next
return dummy.next时间复杂度 O(n)
空间复杂度 O(1)文章来源地址https://www.toymoban.com/news/detail-826590.html
三，步长不一致的快慢指针
两个指针从同侧开始遍历链表，起点一致但步长不一致，直到 fast 指针满足条件退出。
伪代码模板：
fast = head
slow = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next例题：
876. 链表的中间结点 - 力扣（LeetCode）
class Solution:
def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
if not head or not head.next:
return head
slow = head
fast = head
while fast and fast.next:
fast = fast.next.next
slow = slow.next
return slow时间复杂度 O(n)
空间复杂度 O(1)
判断链表中是否含有环：
Floyd 判环算法是快慢指针的经典应用。
使用一个步长为 2 的 fast 指针和一个步长为 1 的 slow 指针，同时从起点出发，如果链表中有环，那么他们一定相遇。
因为在两个指针都进入环后，可以视为在一快一慢跑圈的两个人，速度快的人必定在有限时间内追上速度慢的人，即完成套圈。
快慢指针想遇后，在相遇位置启动一个新指针 A，在链表的 head 位置启动一个指针B，都以步长为 1 的速度移动，则 A，B指针必定在环的入口处相遇。
可以通过运算求证：
设进入环之前的链表长度为 a，环的长度为 L；
在快慢指针运动中，若 slow 指针移动了 S 距离，则 fast 指针移动了 2S 距离；
则 2S - S = S 是快慢指针移动距离的差值；
又因为 fast 与 slow 在环上相遇了，所以 fast 比 slow 多跑了 整数圈
可以设 slow 跑了 n 圈，fast 跑了 m 圈，
如果 slow 与 fast 在 0.6 圈的位置相遇，n = 1.6，m = 5.6
S = a + n * L
2 * S = a + m * L
2 * S - S = S = （m - n）* L
即，S 是环长 L 的整数倍。
此时在该位置启动指针 A，在开始位置启动指针 B；
当 B 走了 a 距离到环的入口位置时，A 走了 S + a 距离；
因为 S 是 环长 L 的整数倍，所以此时 A，B 指针在环的入口位置相遇。
例题：
141. 环形链表 - 力扣（LeetCode）
class Solution:
def hasCycle(self, head: Optional[ListNode]) -> bool:
if not head or not head.next:
return False
fast = head.next
slow = head
while fast != slow:
if not fast or not fast.next:
return False
fast = fast.next.next
slow = slow.next
return True四，分离双指针
两个指针分别属于不同的链表，在不同的链表中移动
伪代码模板：
left_1 = list1
left_2 = list2
while left_1 and left_2:
if 一定条件 1:
left_1 = left_1.next
left_2 = left_2.next
elif 一定条件 2:
left_1 = left_1.next
elif 一定条件 3:
left_2 = left_2.next
例题：
21. 合并两个有序链表 - 力扣（LeetCode）
class Solution:
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
dummy = ListNode()
cur = dummy
left = list1
right = list2
while left and right:
if left.val < right.val:
cur.next = left
left = left.next
else:
cur.next = right
right = right.next
cur = cur.next
if left:
cur.next = left
if right:
cur.next = right
return dummy.next时间复杂度 O(n)文章来源：https://www.toymoban.com/news/detail-826590.html
空间复杂度 O(1)
到了这里，关于数据结构与算法----复习Part 8 （链表双指针）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
