6-2 LinkList2-单链表A拆分成奇数和偶数值单链表B和C【有题解视频，可本地编译器调试】 分数 10 作者 通信DS课程组 单位 成都信息工程大学 在一个带头结点的单链表A中，头指针为a，设计算法SplitList ( )将A分解为两个具有相同结构的链表B、C，其中B表的结点为A表中值为奇数的结点， 而C表的结点为A表中值为偶数的结点（链表A的元素类型为整型，要求B、C表除了头结点可以新开辟空间外，其余结点均利用A表的结点，不得申请新的结点空间）最后要求遍历B，C链表。请编写一下这俄格代码

可以按照以下步骤实现链表 A 的拆分：

1. 新建两个空链表 B 和 C，分别作为奇数值链表和偶数值链表；
2. 遍历链表 A，对于每个节点，判断其值的奇偶性；
3. 如果节点值为奇数，将其从链表 A 中删除，并将其插入链表 B 的尾部；
4. 如果节点值为偶数，将其从链表 A 中删除，并将其插入链表 C 的尾部；
5. 遍历链表 B 和 C，输出它们的值。

具体实现可以参考以下代码（假设链表节点类型为 ListNode，链表头节点为 head）：

def split_list(head):
    b_head = ListNode(None)
    b_tail = b_head
    c_head = ListNode(None)
    c_tail = c_head
    p = head.next
    while p:
        if p.val % 2 == 1:  # 奇数节点
            b_tail.next = p
            b_tail = p
            p = p.next
        else:  # 偶数节点
            c_tail.next = p
            c_tail = p
            p = p.next
    b_tail.next = None
    c_tail.next = None
    return b_head, c_head

# 输出链表中的元素值
def print_list(head):
    p = head.next
    while p:
        print(p.val, end=' ')
        p = p.next
    print()

# 测试代码
a = ListNode(None)
a.append([1, 2, 3, 4, 5, 6, 7, 8, 9])
b, c = split_list(a)
print("B: ", end='')
print_list(b)
print("C: ", end='')
print_list(c)

这个函数的时间复杂度为 O(n)，其中 n 是链表的长度。