这里提供一种解决方法,使用归并排序来对链表进行排序。
首先,定义链表的节点类:
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
然后,实现一个功能函数,用于合并两个有序链表:
def merge(l1, l2):
dummy = ListNode(0) # 创建一个虚拟头节点
curr = dummy # 当前节点指向虚拟头节点
while l1 and l2:
if l1.val <= l2.val:
curr.next = l1
l1 = l1.next
else:
curr.next = l2
l2 = l2.next
curr = curr.next
# 将剩余部分连接到合并后的链表末尾
if l1:
curr.next = l1
elif l2:
curr.next = l2
return dummy.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 = sortList(head) # 递归排序前半部分链表
right = sortList(mid) # 递归排序后半部分链表
return merge(left, right) # 合并两个有序链表
这样,调用sortList
函数即可对链表进行按值排序:
head = ListNode(4)
node1 = ListNode(2)
node2 = ListNode(1)
node3 = ListNode(3)
head.next = node1
node1.next = node2
node2.next = node3
sorted_head = sortList(head)
# 输出排序后的链表
while sorted_head:
print(sorted_head.val)
sorted_head = sorted_head.next
输出结果为:
1
2
3
4