快慢指针的应用单链表
时间: 2025-04-22 09:32:28 浏览: 20
### 快慢指针在单链表中的应用
#### 检测环的存在
快慢指针技术可以用于检测单链表中是否存在环。通过使用两个不同速度移动的指针——一个每次前进一步(慢指针),另一个每次前进步骤多于一次(通常是两步,即快指针)。如果存在环,则这两个指针最终会在某个节点相遇;如果没有环,则快指针会到达链表末端。
```python
def has_cycle(head):
if head is None:
return False
slow = head
fast = head.next
while fast is not None and fast.next is not None:
if slow == fast:
return True
slow = slow.next
fast = fast.next.next
return False
```
此方法的时间复杂度为 O(N),其中 N 是列表长度[^4]。
#### 寻找环起点
当确认了链表中有环之后,还可以利用快慢指针来定位环的具体起始位置。一旦发现两者相交后,将其中一个指针重新指向头结点并让它们都以相同的速度向前走直到再次相遇的地方就是入环的第一个节点。
```python
def detectCycle(head):
if not head or not head.next:
return None
slow, fast = head, head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast: # Cycle detected.
break
else:
return None # No cycle.
ptr1 = head
ptr2 = slow
while ptr1 != ptr2:
ptr1 = ptr1.next
ptr2 = ptr2.next
return ptr1 # Entry point of the cycle.
```
上述算法同样具有线性的平均时间性能表现。
#### 查找中间元素
为了找到给定单向链接数据结构里的中心项,也可以采用双速率迭代器策略。具体来说,在遍历过程中保持一对同步更新的一倍速与二倍速游标,当下者抵达终点时前者正好位于序列正中央处。
```python
def find_middle_node(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow
```
这段代码能够有效地在线性时间内完成任务,并且只需要常量级别的额外空间开销。
阅读全文
相关推荐


















