用程序编写: 使用单链表表示有序表,并进行操作: 1、从键盘输入一组整数,建立第一个有序单链表并输出 2、从键盘输入一组整数,建立第二个有序单链表并输出 3、将两个有序表合并,输出结果 4、输出合并后有序表的中位数
时间: 2024-09-12 19:11:36 浏览: 25
在Python中,我们可以使用内置的数据结构`ListNode`类来表示单链表节点,然后实现相应功能:
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def create_sorted_list(nums):
head = None
tail = None
for num in sorted(nums):
if not head:
head = ListNode(num)
tail = head
else:
tail.next = ListNode(num)
tail = tail.next
return head
def print_linked_list(head):
while head:
print(head.val, end=" -> ")
head = head.next
print("None")
def merge_sorted_lists(list1, list2):
dummy = ListNode(0) # 创建虚拟头节点
current = dummy
while list1 and list2:
if list1.val < list2.val:
current.next = list1
list1 = list1.next
else:
current.next = list2
list2 = list2.next
current = current.next
current.next = list1 or list2
return dummy.next
def find_median(head):
values = []
while head:
values.append(head.val)
head = head.next
values.sort()
n = len(values)
if n % 2 == 0:
median = (values[n // 2 - 1] + values[n // 2]) / 2
else:
median = values[n // 2]
return median
# 示例
nums1 = [1, 3, 5]
nums2 = [2, 4, 6]
list1 = create_sorted_list(nums1)
print_linked_list(list1)
list2 = create_sorted_list(nums2)
print_linked_list(list2)
merged_list = merge_sorted_lists(list1, list2)
print_linked_list(merged_list)
median = find_median(merged_list)
print(f"合并后的中位数是: {median}")
阅读全文