单链表的分解

编写算法创建以整数为数据元素的单向链表，实现将其分解成两个链表，其中一个全部为奇数，另一个全部为偶数（尽量利用已知的存储空间）。

输入格式:

1 2 3 4 5 6 7 8 9 0

输出格式:

1 3 5 7 9 

2 4 6 8 

输入样例:

在这里给出一组输入。例如：

-3 7 6 8 -5 10 2 7 4 0

输出样例:

在这里给出相应的输出。例如：

-3 7 -5 7
6 8 10 2 4

# 定义链表节点类
class Node:def __init__(self, data=None):self.data = dataself.next = None# 定义单向链表类
class LinkedList:def __init__(self):self.head = Node()  # 初始化带头结点# 添加节点到链表尾部def append(self, data):new_node = Node(data)cur = self.headwhile cur.next:  # 找到链表的尾部cur = cur.nextcur.next = new_node# 遍历链表并将元素分成奇数和偶数两个链表def split_odd_even(self):odd_list = LinkedList()  # 存储奇数的链表even_list = LinkedList()  # 存储偶数的链表cur = self.head.next  # 跳过头结点while cur:if cur.data % 2 == 0:  # 偶数even_list.append(cur.data)else:  # 奇数odd_list.append(cur.data)cur = cur.nextreturn odd_list, even_list# 打印链表的所有元素def display(self):cur = self.head.next  # 跳过头结点while cur:print(cur.data, end=" ")cur = cur.nextprint()# 主程序
def main():# 创建初始链表linked_list = LinkedList()# 获取用户输入并构建链表，遇到0结束input_data = input().split()for num in input_data:num = int(num)if num == 0:breaklinked_list.append(num)# 分解链表为奇数链表和偶数链表odd_list, even_list = linked_list.split_odd_even()# 输出奇数链表odd_list.display()# 输出偶数链表even_list.display()# 调用主程序
main()