Python数据结构：有序表的合并

Question

要求输入有序表的数据，利用顺序表和链表结构分布完成两个有序表合并功能，并输出合并后的信息。

Answer 1

在Python中，有序表通常可以使用列表(list)来表示，因为列表是一种内置的数据结构，可以很方便的用来表示顺序表。对于链表，Python没有内置的链表数据结构，但是我们可以自己定义一个简单的链表结构来实现。下面我将演示如何使用顺序表和链表分别完成两个有序表的合并功能。

首先是使用顺序表（列表）来实现：

```python
def merge_sorted_lists(list1, list2):
    result = []
    i, j = 0, 0
    
    # 合并过程
    while i < len(list1) and j < len(list2):
        if list1[i] < list2[j]:
            result.append(list1[i])
            i += 1
        else:
            result.append(list2[j])
            j += 1

    # 处理剩余元素
    while i < len(list1):
        result.append(list1[i])
        i += 1
    while j < len(list2):
        result.append(list2[j])
        j += 1
        
    return result

# 输入有序表的数据
list1 = [int(x) for x in input("输入第一个有序表(空格分隔的整数): ").split()]
list2 = [int(x) for x in input("输入第二个有序表(空格分隔的整数): ").split()]

# 输出合并后的信息
merged_list = merge_sorted_lists(list1, list2)
print("合并后的有序表:", merged_list)
然后是使用链表来实现。首先定义链表的数据结构：

class ListNode:
    def __init__(self, value=0, next=None):
        self.value = value
        self.next = next

def merge_sorted_linked_lists(head1, head2):
    dummy = ListNode()
    current = dummy

    # 合并过程
    while head1 is not None and head2 is not None:
        if head1.value < head2.value:
            current.next = head1
            head1 = head1.next
        else:
            current.next = head2
            head2 = head2.next
        current = current.next

    # 处理剩余元素
    if head1 is not None:
        current.next = head1
    else:
        current.next = head2

    return dummy.next

# 将输入的有序表转换为链表
def list_to_linked_list(lst):
    dummy = ListNode()
    current = dummy
    for val in lst:
        current.next = ListNode(val)
        current = current.next
    return dummy.next

# 输出链表
def print_linked_list(head):
    current = head
    while current:
        print(current.value, end=" -> ")
        current = current.next
    print("None")

# 输入有序表的数据
list1 = [int(x) for x in input("输入第一个有序表(空格分隔的整数): ").split()]
list2 = [int(x) for x in input("输入第二个有序表(空格分隔的整数): ").split()]

# 转换为链表
head1 = list_to_linked_list(list1)
head2 = list_to_linked_list(list2)

# 合并
merged_head = merge_sorted_linked_lists(head1, head2)

# 输出合并后的信息
print("合并后的有序链表:")
print_linked_list(merged_head)

以上就是如何使用顺序表和链表来合并两个有序表的方法。

```