目录

前言：

环形链表

1.单向循环链表

 1.1 创建单向循环链表

 1.2 单向循环链表的转置

2.双向循环链表

2.1 双向循环链表的创建

3.局部环形链表（单向）

前言：

        上一期讲了单链表的建立，增删改查以及转置，那这一期我们进一步学习链表，也就是环形链表，其中包括单向循环链表以及双向循环链表还有局部循环，下面就一期来看看吧！

上一期链接：Python数据结构-----链表1.0（单链表的增删改查以及反转）_Python欧尼酱的博客-CSDN博客

环形链表

 环形链表，顾名思义就是形成了一个环的链表，头尾相连，所以没有头也没有尾，如图所示：

 环形链表包括很多种，这里我就介绍单向循环链表，双向循环链表以及局部循环链表

1.单向循环链表

单向循环链表也就是只有一个方向，且头尾相连，形成一个单向换，如上图所示，由于单向循环链表的增删改查操作基本上跟单链表一模一样，所以这里我就只讲解单向循环链表的建立和实现单向循环链表的转置输出

 1.1 创建单向循环链表

        非常简单，我们只需要在原来单链表的基础上，把最后一个节点的指针域指向头结点就OK了。当然，由于这是环形链表，没头没尾，所以我建议在数据域里面添加一个下标作为标记，以方便我们去查找

代码如下：

#建立节点对象
class Listnode(object):def __init__(self,data=0,count=1,next=None):self.data=dataself.count=count#设置一个count作为标记,初始为1，表示第一节点self.next=next
#创建链表对象
class List(object):def __init__(self):self.head=None# 创建单向循环链表def create(self,alldata):count=1self.head=Listnode(alldata[0],count) #头结点的标记为1cur=self.headfor i in alldata[1:]:count+=1 #每次创建一个节点就给标记加一p=Listnode(i,count)cur.next=pcur=pcur.next=self.head#这里吧最后一个节点的指针指向头结点return self.head

这样就成功创建了一个链表对象，可以调用里面的create()方法来创建一个单向循环链表

 1.2 单向循环链表的转置

        给定一个单向循环链表，那我们怎么去实现这个单向循环链表转置呢？方法非常简单，这里我提供两个方法：

方法一：我们只需要把这个单向循环链表变回单链表就OK了，然后进行转置，再把最后一个节点指向头结点就行了。

方法二：我们可以去通过标记把环形链表看做单链表来实现转置

这里我比较建议去用方法二，可以提高效率，完整代码如下：

#建立节点对象
class Listnode(object):def __init__(self,data=0,count=1,next=None):self.data=dataself.count=count#设置一个count作为标记,初始为1，表示第一节点self.next=next
#创建链表对象
class List(object):def __init__(self):self.head=None# 创建单向循环链表def create(self,alldata):count=1self.head=Listnode(alldata[0],count)cur=self.headfor i in alldata[1:]:count+=1p=Listnode(i,count)cur.next=pcur=pcur.next=self.headreturn self.head #返回标记为1的节点（头结点）#单向循环链表的转置def reverse(self):p=self.head.next #初始化基本上是一样的self.head.next=None #断开链表，第一个节点指向空g=self.head #标记第一个节点count=2 #开始计数，从第二个节点开始while count==p.count:q=p.nextp.next=self.headself.head=pp=qcount+=1 #每次计数+1，直到最后一个位置的节点转置完成g.next=self.head #把之前标记的第一个节点指向新的头节点，成环

2.双向循环链表

双向循环，也就是说在单向循环的基础上再加上一个循环方向，对比于单向循环链表，双向循环链表完全就是没有头和尾了，同样我们也是用数字进行节点依次标记，方便我们进行相关的操作，这里我主要去讲解怎么创建双向循环链表，其他的增删改查也是跟单链表一样的，就不讲了

2.1 双向循环链表的创建

要想创建一个双向循环链表，那就意味着要增加一个前指针，prv，依次把前面的节点连起来，然后成环，做法基本上跟单向循环链表建立是一样的，无非就是在单向循环链表再添加是一个‘单向循环链表’。

双向循环链表单个节点如图所示： 

#建立节点对象
class Listnode(object):def __init__(self,data=0,count=1,prv=None,next=None):self.data=dataself.count=count#设置一个count作为标记,初始为1，表示第一节点self.prv=prv #设置一个前指针self.next=next
#创建链表对象
class List(object):def __init__(self):self.head=None# 创建双向循环链表def create(self,alldata):count=1self.head=List(alldata[0],count)cur=self.headfor i in alldata[1:]:count+=1p=Listnode(i,count)p.prv=cur #把新建立的节点前指针指向上一个节点cur.next=p #把上一个节点的后指针指针指向新的节点cur=p#成环cur.next=self.head #把最后一个节点的后指针指向头节点self.head.prv=cur #把头节点的前指针指向最后一个节点return self.head

3.局部环形链表（单向）

什么是局部环形链表呢？其实就是在单链表的基础上，把最后一个节点指向链表中的某一个节点（注意不是头节点，指向头节点就是环形链表），如图所示：

这就是一个非常直观的局部环形链表了

 但是这一类链表是有头没有尾的，或者有尾没有头，同样我们还是采样标记法去标记每一个节点，以方便我们操作，这里就讲解怎么去建立局部环形链表。

代码如下：

#建立节点对象
class Listnode(object):def __init__(self,data=0,count=1,next=None):self.data=dataself.count=count#设置一个count作为标记,初始为1，表示第一节点self.next=next
#创建链表对象
class List(object):def __init__(self):self.head=None# 创建双向循环链表def create(self,alldata,index): #index是表示要在第index个节点成环count=1self.head=List(alldata[0],count)cur=self.headfor i in alldata[1:]:count+=1p=List(i,count)cur.next=pcur=p#上面这里就建立了一个单链表，下面就进行成环处理p=self.headwhile p:if p.count==index: #当找到这个位置时就把最后一个节点指向这个节点cur.next=pbreakelse:p=p.nextreturn self.head

OK，这一期就先到这里了，我们下次见！

分享一张壁纸：