极客笔记从循环链表的末尾删除节点的Python程序
在循环链表中，节点之间的关系是首尾相连的，即最后一个节点指向第一个节点，形成一个环形结构。如何从循环链表的末尾删除节点呢？下面将介绍一种Python程序的实现方法。
更多Python相关文章，请阅读：Python 教程
1. 创建循环链表
为了方便演示，我们先创建一个简单的循环链表。下面的代码使用链表节点Node和循环链表CircularLinkedList实现了一个包含5个节点的循环链表。
class Node:
def __init__(self, data):
self.data = data
self.next = None
class CircularLinkedList:
def __init__(self):
self.head = None
def add(self, data):
node = Node(data)
if not self.head:
self.head = node
node.next = self.head
else:
cur = self.head
while cur.next != self.head:
cur = cur.next
cur.next = node
node.next = self.head
def __str__(self):
cur = self.head
s = ''
while cur:
s += str(cur.data) + ' -> '
cur = cur.next
if cur == self.head:
break
s += 'head'
return s
现在我们创建一个CircularLinkedList对象，添加5个节点。
cll = CircularLinkedList()
cll.add(1)
cll.add(2)
cll.add(3)
cll.add(4)
cll.add(5)
print(cll)
输出结果为：
1 -> 2 -> 3 -> 4 -> 5 -> head
2. 从末尾删除节点
我们可以使用两个指针来遍历循环链表，一个指向要删除的节点，另一个指向要删除节点的前一个节点。当第一个指针到达链表末尾时，第二个指针就指向要删除节点的前一个节点了。具体实现如下：
def delete_last_node(self):
if not self.head:
return None
if self.head.next == self.head:
data = self.head.data
self.head = None
return data
cur = self.head
while cur.next != self.head:
pre = cur
cur = cur.next
pre.next = cur.next
data = cur.data
return data
在delete_last_node()函数中，首先判断链表是否为空，如果为空，则返回None。如果链表只有一个节点，将该节点删除，并返回该节点的数据。否则，使用cur指针遍历链表，pre指针始终指向cur的前一个节点，当cur指针到达链表末尾时，pre指针就指向了要删除节点的前一个节点。最后，将pre节点的next指针指向cur节点的next节点，也就是删除cur节点。然后返回删除节点的数据。如果要删除多个节点，可以在delete_last_node()函数中多次调用。
现在我们使用delete_last_node()函数从循环链表的末尾删除2个节点，代码如下：
print(cll.delete_last_node())
print(cll.delete_last_node())
输出结果为：
5
4
我们可以打印一下循环链表，看看节点是否被成功删除。
print(cll)
输出结果为：
1 -> 2 -> 3 -> head
可以看到，从循环链表的末尾成功删除了两个节点。
3. 完整代码
下面是完整的Python程序代码：
class Node:
def __init__(self, data):
self.data = data
self.next = None
class CircularLinkedList:
def __init__(self):
self.head = None
def add(self, data):
node = Node(data)
if not self.head:
self.head = node
node.next = self.head
else:
cur = self.head
while cur.next != self.head:
cur= cur.next
cur.next = node
node.next = self.head
def delete_last_node(self):
if not self.head:
return None
if self.head.next == self.head:
data = self.head.data
self.head = None
return data
cur = self.head
while cur.next != self.head:
pre = cur
cur = cur.next
pre.next = cur.next
data = cur.data
return data
def __str__(self):
cur = self.head
s = ''
while cur:
s += str(cur.data) + ' -> '
cur = cur.next
if cur == self.head:
break
s += 'head'
return s
cll = CircularLinkedList()
cll.add(1)
cll.add(2)
cll.add(3)
cll.add(4)
cll.add(5)
print(cll.delete_last_node())
print(cll.delete_last_node())
print(cll)
结论
本文介绍了Python程序从循环链表的末尾删除节点的实现方法。首先，我们需要创建一个循环链表，并实现一个删除末尾节点的方法。在删除节点时，可以使用两个指针来遍历循环链表，一个指向要删除的节点，另一个指向要删除节点的前一个节点。当第一个指针到达链表末尾时，第二个指针就指向要删除节点的前一个节点了。最后，将前一个指针的next指针指向要删除节点的下一个节点，也就是删除该节点。