单链表之快慢指针

单链表的快慢指针简介

• 快慢指针指链表中定义两个指针，两个指针的移动速度一快一慢，一般快指针移动步长为慢指针的两倍

快慢指针适合解决的几个典型问题

中间值问题

单向链表是否有环问题

有环链表的入口问题

先定义一个简单的节点

class Node:def __init__(self, item):self.item = itemself.next = Nonefirst = Node('aa') second = Node('bb') third = Node('cc') forth = Node('dd') fifth = Node('ee')first.next = second second.next = third third.next = forth forth.next = fifth

中间值问题
即当快指针fast遍历完链表时，慢指针slow刚好停在链表的中间处

def middle(first):fast = firstslow = firstwhile fast.next and fast.next.next:fast = fast.next.nextslow = slow.nextreturn slowprint(f"The middle is: {middle(first).item}")

中间位置对应的结点是cc

有环链表

• 有环链表定义：单链表中存在结点的指针往前指的链表称为有环链表
  

# 接上面定义结点的代码 # Create a ring fifth.next = third def has_ring(first):fast = firstslow = firstwhile fast.next and fast.next.next:fast = fast.next.nextslow = slow.nextif fast == slow:return Truereturn Falseprint(f"Is there a ring in the list? {has_ring(first)}")

为链表创建一个环，执行has_ring函数返回True，注释创建的环，则返回False

有环链表入口

• 定义：当快慢指针相遇时，我们可以判定链表中存在环，此时，重新定义一个指针，指向链表的起点，这个指针的前进步长与慢指针的相同，当慢指针与“新”指针相遇时，所在节点就是环的入口

证明这一结点设计到数论知识，有兴趣可以研究，这里只进行实现
在有环链表的前提上，使用以下代码可判断环的入口

def get_the_entrance(first):# Create a new pointer, pointing to the beginningtemp = firstfast = firstslow = firstwhile fast.next and fast.next.next:fast = fast.next.nextslow = slow.nextif fast == slow:while True:temp = temp.nextslow = slow.nextif temp == slow:return tempprint(f"The entrance is: {get_the_entrance(first).item}")

前面的有环链表时aa→bb→cc→dd→ee(→cc)，因此其环入口是cc对应所在的节点
The entrance is: cc

创作挑战赛新人创作奖励来咯，坚持创作打卡瓜分现金大奖

总结

以上是生活随笔为你收集整理的数据结构链表之单链表的快慢指针——3的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。