双指针：快慢指针
应用快慢指针模式原地删除重复项、移动零元素，并围绕枢轴值对数组进行分区。
双指针：快慢指针 是 CoddyKit 上的免费 DSA Interview Prep 课时。 这是第 4 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 DSA Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 DSA Interview Prep 课程共包含 4 节课。
快慢指针详解
快慢指针模式（也称龟兔算法）使用两个速度不同的指针在同一个序列中移动。与相向指针不同，两者都从开头开始。慢指针每次前进一个步骤；快指针每次前进两个或更多步骤。速度差会产生有用的不变量：慢指针跟踪一个“有效前缀”，而快指针向前扫描以查找满足条件的位置。
# Slow pointer marks the write position;
# Fast pointer scans for next non-duplicate.
def remove_duplicates(nums):
if not nums: return 0
slow = 0 # next position to write a unique value
for fast in range(1, len(nums)):
if nums[fast] != nums[slow]:
slow += 1
nums[slow] = nums[fast]
return slow + 1 # new length
nums = [1, 1, 2, 3, 3, 3, 4]
k = remove_duplicates(nums)
print(nums[:k]) # [1, 2, 3, 4]从有序数组中删除重复项
在有序数组中，重复项彼此相邻。慢指针跟踪最近写入的唯一值；快指针向前扫描。每当快指针遇到一个不同于 nums[slow] 的值时，就推进慢指针并复制这个新值。该原地算法的时间复杂度为 O(n)，额外空间复杂度为 O(1)，是检验读写指针模式掌握程度的经典面试题。
def remove_duplicates_v2(nums):
slow = 0
for fast in range(len(nums)):
if nums[fast] != nums[slow]:
slow += 1
nums[slow] = nums[fast]
return slow + 1
# Allow at most 2 occurrences
def remove_duplicates_k2(nums):
slow = 0
for fast in range(len(nums)):
if slow < 2 or nums[fast] != nums[slow - 2]:
nums[slow] = nums[fast]
slow += 1
return slow
print(remove_duplicates_k2([1,1,1,2,2,3]))
# Result: 5, nums[:5] = [1,1,2,2,3]使用快慢指针移动零值
将所有零值移动到末尾，同时保持非零元素的相对顺序。慢指针标记下一个非零元素应放置的位置。快指针扫描非零值。快指针找到非零值时，将其复制到慢指针的位置，然后同时推进两个指针。扫描结束后，将从慢指针到末尾的位置填充为零值。时间复杂度为 O(n)，空间复杂度为 O(1)。
def move_zeroes(nums):
slow = 0 # next position for a non-zero
for fast in range(len(nums)):
if nums[fast] != 0:
nums[slow] = nums[fast]
slow += 1
# Fill rest with zeroes
while slow < len(nums):
nums[slow] = 0
slow += 1
nums = [0, 1, 0, 3, 12]
move_zeroes(nums)
print(nums) # [1, 3, 12, 0, 0]围绕枢轴元素对数组进行分区
快速排序的分区子步骤会原地重新排列元素，使所有 < pivot 的值位于 >= pivot 的值之前。Lomuto 方案使用慢指针（标记最后一个较小元素的位置）和快指针（向前扫描）。当快指针找到较小元素时，递增慢指针并交换两个元素。该过程的时间复杂度为 O(n)，额外空间复杂度为 O(1)。
def lomuto_partition(nums, low, high):
pivot = nums[high]
slow = low - 1 # last position of small element
for fast in range(low, high):
if nums[fast] <= pivot:
slow += 1
nums[slow], nums[fast] = nums[fast], nums[slow]
# Place pivot in final position
nums[slow+1], nums[high] = nums[high], nums[slow+1]
return slow + 1 # pivot's final index
arr = [3, 1, 4, 1, 5, 9, 2, 6]
p = lomuto_partition(arr, 0, len(arr)-1)
print(arr) # elements before p are <= pivot查找链表的中间节点
在链表上使用快慢指针时，快指针每一步前进两个节点，慢指针前进一个节点。当快指针到达末尾时，慢指针正好位于中间位置。这种 O(n) 的单次扫描方法比先统计节点数、再走到一半更加简洁。它被用作链表归并排序以及链表回文检测的子步骤。
class Node:
def __init__(self, val, nxt=None):
self.val = val
self.next = nxt
def find_middle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow # slow is at middle
# Build 1->2->3->4->5
h = Node(1, Node(2, Node(3, Node(4, Node(5)))))
mid = find_middle(h)
print(mid.val) # 3 (middle of 5 nodes)环检测：弗洛伊德龟兔算法
弗洛伊德环检测算法将慢指针和快指针放在链表头部。慢指针前进一个节点；快指针前进两个节点。如果存在环，快指针最终会追上慢指针，两者将在环内相遇。如果快指针到达空值，则不存在环。之所以一定会相遇，是因为每次迭代中快指针都会比慢指针多前进一步——对于长度为 k 的环，从慢指针进入环开始，最多 k 步内两者就会相遇。
class ListNode:
def __init__(self, val=0, nxt=None):
self.val = val
self.next = nxt
def has_cycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow is fast: # identity check (same object)
return True
return False
# 1->2->3->4->2 (cycle at node 2)
n1 = ListNode(1)
n2 = ListNode(2)
n3 = ListNode(3)
n4 = ListNode(4)
n1.next=n2; n2.next=n3; n3.next=n4; n4.next=n2
print(has_cycle(n1)) # True查找环的入口节点
检测到环（即两指针相等）后，将其中一个指针重置到头部。现在让两个指针每次各前进一步。它们会在环的入口节点相遇。这利用了一个数学性质：从头部到环入口的距离，等于从相遇点到环入口的距离（以环长度为模）。这是一个优美的数学结论，经常出现在高难度面试题中。
def detect_cycle(head):
slow = fast = head
# Phase 1: detect
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow is fast:
break
else:
return None # no cycle
# Phase 2: find entry
slow = head
while slow is not fast:
slow = slow.next
fast = fast.next
return slow # cycle entry node
# Using same cycled list as previous scene
print(detect_cycle(n1).val) # 2 (cycle entry)使用快慢指针判断快乐数
快慢指针不仅适用于链表，也适用于任何会形成循环的过程。“快乐数”会在各位数字平方和组成的序列中循环——如果 n 不是快乐数，该序列最终会进入循环。使用慢指针（一步表示计算一次各位数字平方和）和快指针（每次计算两步）来检测循环。如果两者在 1 处相遇，n 就是快乐数；否则它会陷入一个不包含 1 的循环。这是将弗洛伊德算法应用于数值虚拟链表。
def is_happy(n):
def next_val(x):
total = 0
while x:
x, d = divmod(x, 10)
total += d * d
return total
slow = n
fast = next_val(n)
while fast != 1 and slow != fast:
slow = next_val(slow)
fast = next_val(next_val(fast))
return fast == 1
print(is_happy(19)) # True (1->9->...->1)
print(is_happy(2)) # False (enters a cycle)从链表末尾查找第 n 个节点
使用两个指针单次扫描，即可找到链表中从末尾开始的第 n 个节点。先让快指针向前移动 n 步。然后同时推进两个指针，直到快指针到达末尾——此时慢指针位于从末尾开始的第 n 个节点。要删除该节点，请保留一个位于慢指针前一步的“前驱”指针。这是经典的单次扫描链表问题，无需先统计链表总长度。
def remove_nth_from_end(head, n):
dummy = ListNode(0)
dummy.next = head
fast = slow = dummy
# Advance fast n+1 steps
for _ in range(n + 1):
fast = fast.next
# Advance together
while fast:
slow = slow.next
fast = fast.next
# slow.next is the nth from end
slow.next = slow.next.next
return dummy.next
# Build 1->2->3->4->5, remove 2nd from end
h2 = ListNode(1,ListNode(2,ListNode(3,ListNode(4,ListNode(5)))))
result = remove_nth_from_end(h2, 2)
# Should give 1->2->3->5字符串问题中的快慢指针
快慢指针的思路同样适用于数组和字符串问题。压缩游程编码字符串时，慢指针标记写入位置，快指针扫描到每段游程的末尾。当游程中的所有字符都等于慢指针所指的字符时，推进快指针；否则记录该游程并更新慢指针。这样即可在单次扫描中以 O(n) 时间和 O(1) 空间完成处理。
def compress(chars):
slow = fast = 0
while fast < len(chars):
char = chars[fast]
count = 0
# Count the run
while fast < len(chars) and chars[fast] == char:
fast += 1
count += 1
chars[slow] = char
slow += 1
if count > 1:
for c in str(count):
chars[slow] = c
slow += 1
return slow
chars = list('aabcccccaa')
print(compress(chars)) # 6
print(chars[:6]) # ['a','2','b','c','5','a']... wait
# Actually: ['a','2','b','c','5','a','2']如何选择快慢指针与相向双指针
当问题涉及和为目标值的数对、回文检查，或需要从两侧收窄窗口时，请使用相向指针。当需要使用写入指针（删除或移动元素）、处理链表结构（中间节点、环），或检测任意数值序列中的循环时，请使用快慢指针。两者都能消除嵌套循环并达到 O(n) 时间复杂度——决定因素是遍历的结构。
# Pattern matcher:
# 1. Sorted array, target sum -> OPPOSITE ENDS
# 2. Remove/filter elements in-place -> SLOW-FAST (read-write)
# 3. Linked list middle/cycle -> SLOW-FAST (1x vs 2x speed)
# 4. Detect cycle in value sequence -> SLOW-FAST (Floyd)
# Example: given sorted array, remove val in-place
def remove_sorted(nums, val):
slow = 0
for fast in range(len(nums)):
if nums[fast] != val:
nums[slow] = nums[fast]
slow += 1
return slow
nums = [0,1,2,2,3,0,4,2]
print(remove_sorted(nums, 2)) # 5快速检查
测试您对本课中“数据结构与算法——编程面试准备”相关概念的理解。
课程回顾
本课中您学到了：快慢（读写）模式让写入指针始终指向下一个有效位置，同时让快指针向前扫描，是原地删除、去重和移动零值的基础，弗洛伊德龟兔算法利用两个指针之间的速度差，以 O(n) 时间和 O(1) 空间检测循环，以及检测到循环后，将一个指针重置到头部，再让两个指针以相同速度前进，就能根据可证明的距离相等关系找到环入口。接下来我们将学习适用于面试的 Python 字符串 API。
常见问题解答
「双指针：快慢指针」课时是免费的吗？
是的 — 「双指针：快慢指针」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 DSA Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 DSA Interview Prep 课程共包含 4 节课。
「双指针：快慢指针」这节课中我会学到什么？
应用快慢指针模式原地删除重复项、移动零元素，并围绕枢轴值对数组进行分区。 你通过在浏览器中直接运行的动手代码来练习 DSA Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 DSA Interview Prep 需要有经验吗？
无需任何先前经验。CoddyKit 上的 DSA Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 4 节课，共 4 节。
「双指针：快慢指针」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 DSA Interview Prep 课中编写并运行代码吗？
能。每节 DSA Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。
此课程中的所有课时
- 数组基础与原地操作
- 前缀和与累计总和
- 双指针：从两端向中间
- 双指针：快慢指针