数据结构归并排序代码链表完整版
时间: 2024-10-11 19:12:31 浏览: 5
合并排序是一种分治算法,它通常用于对数组进行排序,但对于链表同样适用。这里是一个链表版本的归并排序示例,使用递归的方式来实现:
```python
# 定义链表节点
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def merge_sort_linked_list(head):
# 归并排序的基本情况,只有一个元素或者空链表
if not head or not head.next:
return head
# 找到链表中间位置
mid = get_middle(head)
# 分割链表
left_half = head
right_half = mid.next
mid.next = None
# 对左右两半分别进行归并排序
left_sorted = merge_sort_linked_list(left_half)
right_sorted = merge_sort_linked_list(right_half)
# 合并已排序的链表
sorted_head = merge(left_sorted, right_sorted)
return sorted_head
def get_middle(head):
if not head:
return head
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow
def merge(left, right):
dummy = ListNode(0) # 创建一个虚拟头节点
current = dummy
while left and right:
if left.val < right.val:
current.next = left
left = left.next
else:
current.next = right
right = right.next
current = current.next
# 将剩余部分添加到结果链表
current.next = left if left else right
return dummy.next
# 示例链表排序
head = ListNode(4, ListNode(2, ListNode(1, ListNode(3))))
sorted_head = merge_sort_linked_list(head)
```