中小型网站建设市场,开发一个小软件多少钱,服装店设计,建设银行网站上的的研究报告单链表之快慢指针
单链表的快慢指针简介
快慢指针指链表中定义两个指针#xff0c;两个指针的移动速度一快一慢#xff0c;一般快指针移动步长为慢指针的两倍
快慢指针适合解决的几个典型问题
中间值问题单向链表是否有环问题有环链表的入口问题
先定义一个简单的节点
…单链表之快慢指针
单链表的快慢指针简介
快慢指针指链表中定义两个指针两个指针的移动速度一快一慢一般快指针移动步长为慢指针的两倍
快慢指针适合解决的几个典型问题
中间值问题单向链表是否有环问题有环链表的入口问题
先定义一个简单的节点
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(fThe 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(fIs 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(fThe entrance is: {get_the_entrance(first).item})前面的有环链表时aa→bb→cc→dd→ee(→cc)因此其环入口是cc对应所在的节点 The entrance is: cc
