Python 单链表操作：交集、并集、倒序、合并与复制

本文将使用 Python 实现单链表的基本操作，包括求两个链表的交集和并集，将其中一个链表倒序，合并两个有序链表并复制合并后的链表。

代码：

# 定义单链表节点
class ListNode:
    def __init__(self, value):
        self.val = value
        self.next = None

# 定义插入节点函数
def insert_node(head, value):
    new_node = ListNode(value)
    if head is None or value >= head.val:
        new_node.next = head
        return new_node
    else:
        cur = head
        while cur.next and cur.next.val > value:
            cur = cur.next
        new_node.next = cur.next
        cur.next = new_node
        return head

# 创建链表 a
a = None
print('请输入5个整数（用空格分隔）：')
a_values = list(map(int, input().split()))
for num in a_values:
    a = insert_node(a, num)

# 创建链表 b
b = None
print('请输入5个整数（用空格分隔）：')
b_values = list(map(int, input().split()))
for num in b_values:
    b = insert_node(b, num)

# 输出链表 a 和 b 的交集和并集
intersection = []
union = []
cur_a = a
cur_b = b
while cur_a and cur_b:
    if cur_a.val == cur_b.val:
        intersection.append(cur_a.val)
        union.append(cur_a.val)
        cur_a = cur_a.next
        cur_b = cur_b.next
    elif cur_a.val < cur_b.val:
        union.append(cur_a.val)
        cur_a = cur_a.next
    else:
        union.append(cur_b.val)
        cur_b = cur_b.next

while cur_a:
    union.append(cur_a.val)
    cur_a = cur_a.next

while cur_b:
    union.append(cur_b.val)
    cur_b = cur_b.next

print('链表a和b的交集为:', intersection)
print('链表a和b的并集为:', union)

# 将链表 b 倒序
prev = None
cur = b
while cur:
    temp = cur.next
    cur.next = prev
    prev = cur
    cur = temp
b = prev

# 合并两个有序链表为一个有序链表（从大到小排序）
def merge_sorted_lists(a, b):
    dummy = ListNode(0)
    cur = dummy
    while a and b:
        if a.val >= b.val:
            cur.next = a
            a = a.next
        else:
            cur.next = b
            b = b.next
        cur = cur.next
    if a:
        cur.next = a
    if b:
        cur.next = b
    return dummy.next

merged = merge_sorted_lists(a, b)

# 复制合并后的链表
dummy = ListNode(0)
cur = dummy
while merged:
    cur.next = ListNode(merged.val)
    cur = cur.next
    cur.next = ListNode(merged.val)
    cur = cur.next
    merged = merged.next

# 输出复制后的链表
cur = dummy.next
result = []
while cur:
    result.append(cur.val)
    cur = cur.next

print('合并后的有序链表为:', result)

代码解析：

定义单链表节点:
- ListNode 类定义了单链表节点，包含 val 属性存储节点的值和 next 属性指向下一个节点。
定义插入节点函数:
- insert_node 函数将新节点插入到已排序的单链表中，保持链表的排序顺序。
创建链表 a 和 b:
- 使用用户输入的 5 个整数创建两个链表。
求链表 a 和 b 的交集和并集:
- 使用两个指针分别遍历两个链表，比较节点值，将相同值添加到交集列表，将所有值添加到并集列表。
将链表 b 倒序:
- 使用三个指针 prev, cur 和 temp 遍历链表，将 cur 指针的 next 指针指向 prev，然后将 prev 指针指向 cur，最后将 cur 指针指向 temp。
合并两个有序链表为一个有序链表:
- 使用 merge_sorted_lists 函数合并两个有序链表，将合并后的链表返回。
复制合并后的链表:
- 使用循环遍历合并后的链表，将每个节点的值复制到新的链表中。
输出复制后的链表:
- 使用循环遍历复制后的链表，将每个节点的值输出到列表中。

运行结果:

用户输入 5 个整数创建链表 a，再输入 5 个整数创建链表 b，代码将输出链表 a 和 b 的交集、并集、合并后的有序链表和复制后的链表。

总结:

本文介绍了使用 Python 实现单链表的基本操作，包括求交集、并集、倒序、合并和复制等操作。这些操作在实际开发中经常用到，希望本文能帮助您更好地理解单链表的基本操作。