Python实现循环单链表就是在链表的基础上，使得尾节点的next指针指向头结点，因此在代码上和单链表有着一定的相似之处。
单链表实现
https://blog.csdn.net/weihuan2323/article/details/124673571
首先我们还是要先定义一个node类，用于存放链表中的节点
class Node():
"""节点"""
def __init__(self, data):
self.data = data
self.next = None有了node类，我们便可以以它为基础构建循环单链表。
对该循环单链表我定义了如下几个函数：
- isEmpty()
- length()
- show()
- add()
- append()
- insert()
- remove()
- search()
- locate()
具体作用有注释介绍
class CircularLinkedlist():
"""单向循环链表"""
def __init__(self):
self.head = None
def isEmpty(self):
"""判断链表是否为空"""
return self.head == None
def length(self):
"""返回链表的长度"""
# 如果链表为空，返回长度0
if self.isEmpty():
return 0
count = 1
cur = self.head
while cur.next != self.head:
count += 1
cur = cur.next
return count
def show(self):
"""遍历链表"""
if self.isEmpty():
return " "
cur = self.head
result = "head" + "-->" + str(cur.data)
while cur.next != self.head:
cur = cur.next
data = cur.data
result = result + "-->" + str(data)
return result
def add(self, data):
"""头部添加节点"""
node = Node(data)
if self.isEmpty():
self.head = node
node.next = self.head
else:
# 添加的节点指向head
node.next = self.head
# 移到链表尾部，将尾部节点的next指向node
cur = self.head
while cur.next != self.head:
cur = cur.next
cur.next = node
# head指向添加node的
self.head = node
def append(self, data):
"""尾部添加节点"""
node = Node(data)
if self.isEmpty():
self.head = node
node.next = self.head
else:
# 移到链表尾部
cur = self.head
while cur.next != self.head:
cur = cur.next
# 将尾节点指向node
cur.next = node
# 将node指向头节点head
node.next = self.head
def insert(self, index, data):
"""在指定位置添加节点"""
# 小于0在头部添加
if index <= 0:
self.add(data)
# 大于长度在尾部添加
elif index > (self.length() - 1):
self.append(data)
else:
node = Node(data)
cur = self.head
count = 0
# 移动到指定位置的前一个位置
while count < (index - 1):
count += 1
cur = cur.next
node.next = cur.next
cur.next = node
def remove(self, data):
"""删除一个节点"""
# 若链表为空，则直接返回
if self.isEmpty():
raise IndexError("链表为空，删除失败")
# 将cur指向头节点
cur = self.head
pre = None
# 若头节点的元素就是要查找的元素data
if cur.data == data:
# 如果链表不止一个节点
if cur.next != self.head:
# 先找到尾节点，将尾节点的next指向第二个节点
while cur.next != self.head:
cur = cur.next
# cur指向了尾节点
cur.next = self.head.next
self.head = self.head.next
else:
# 链表只有一个节点
self.head = None
else:
pre = self.head
# 第一个节点不是要删除的
while cur.next != self.head:
# 找到了要删除的元素
if cur.data == data:
# 删除
pre.next = cur.next
return
else:
pre = cur
cur = cur.next
# cur 指向尾节点
if cur.data == data:
# 尾部删除
pre.next = cur.next
def search(self, data):
"""查找节点是否存在"""
if self.isEmpty():
return False
cur = self.head
if cur.data == data:
return True
while cur.next != self.head:
cur = cur.next
if cur.data == data:
return True
return False
def locate(self,index):
'''找到索引位置为index的node'''
if self.isEmpty():
raise IndexError("链表为空")
p = self.head
j = 0
while (p != None and j < index):
j += 1
p = p.next
if (j == index):
return p
else:
return None定义完成循环单链表，那我们便可以尝试解决一下约瑟夫环问题。相较于线性表来说，使用循环单链表会相对简单一些。
约瑟夫环（Josephus）：设
n
个人围坐在一个圆桌周围，现在从第
s
个人开始报数，数到第
m
个人，让他出局；然后从出局的下一个人重新开始报数，数到第
m
个人，再让他出局，……，如此反复直到所有的人全部出局为止。要解决的Josephus问题是：对于任意给定的
n
,
s
和
m
，求出这
n
个人的出局序列。
if __name__ == "__main__":
print("循环单链表约瑟夫环".center(40,'-'))
n = int(input("请输入总人数："))
s = int(input("请输入从第几个人开始报数："))
m = int(input("请输入数到第几个人出局："))
mylinklist = CircularLinkedlist()
for i in range(1, n+1):
mylinklist.append(i)
result = []
count = 1
cur = mylinklist.locate(s-1)
while cur != cur.next :
cur = cur.next
count += 1
if count == m:
result.append(cur.data)
mylinklist.remove(cur.data)
count = 0
#往结果中加入剩下的头结点
result.append(mylinklist.head.data)
print(f"\n死亡顺序为：{result}")