给我一个带头结点尾插法的链表程序
时间: 2024-09-20 15:08:55 浏览: 38
头结点尾插法是一种常用于操作链表的数据结构技术,它可以在O(1)的时间复杂度内将一个新元素插入到已排序链表的末尾,保持链表始终有序。以下是使用Python语言的一个简单示例:
```python
class Node:
def __init__(self, value):
self.value = value
self.next = None
class SortedLinkedList:
def __init__(self):
self.head = Node(None)
def insert(self, value):
new_node = Node(value)
# 如果链表为空或者新值小于当前节点,我们需要插入在头部
if not self.head.next or value < self.head.next.value:
new_node.next = self.head.next
self.head.next = new_node
else:
current = self.head.next
while current.next and current.next.value < value:
current = current.next
# 插入新节点在找到的适当位置
new_node.next = current.next
current.next = new_node
# 使用示例
list = SortedLinkedList()
list.insert(5) # [5]
list.insert(2) # [2, 5]
list.insert(8) # [2, 5, 8]
```
在这个例子中,`SortedLinkedList`类有`head`作为头节点,并包含一个`insert`方法。当插入新值时,我们创建一个新的节点并检查是否需要将其放在头节点之后(如果链表空或新值小于现有最小值),或者在链表的适当位置(通过循环找到第一个大于等于新值的位置)。
阅读全文