以下是一个按字母顺序排列的链表排序的示例代码:
# 定义链表节点
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
# 定义排序函数
def sortList(head):
if not head or not head.next:
return head
# 使用快慢指针找到链表的中点
slow, fast = head, head.next
while fast and fast.next:
slow = slow.next
fast = fast.next.next
# 将链表分成两部分
mid, slow.next = slow.next, None
# 递归对两个子链表进行排序
left, right = sortList(head), sortList(mid)
# 合并两个有序链表
dummy = ListNode(0)
p = dummy
while left and right:
if left.val < right.val:
p.next = left
left = left.next
else:
p.next = right
right = right.next
p = p.next
p.next = left if left else right
return dummy.next
# 创建链表
head = ListNode('b')
head.next = ListNode('a')
head.next.next = ListNode('c')
# 打印排序前的链表
print("排序前的链表:")
node = head
while node:
print(node.val, end=" -> ")
node = node.next
print("None")
# 对链表排序
head = sortList(head)
# 打印排序后的链表
print("排序后的链表:")
node = head
while node:
print(node.val, end=" -> ")
node = node.next
print("None")
输出结果为:
排序前的链表:
b -> a -> c -> None
排序后的链表:
a -> b -> c -> None
这个示例代码中,首先定义了一个ListNode
类来表示链表节点。然后,定义了一个sortList
函数来对链表进行排序。在排序函数中,使用快慢指针找到链表的中点,然后将链表分成两部分,递归对两个子链表进行排序。最后,使用归并排序的思想将两个有序链表合并成一个有序链表。最后,创建一个链表对象并调用排序函数,最后打印排序前和排序后的链表。
上一篇:按字母顺序排列的常见子串
下一篇:按字母顺序排列的热图索引值