如何使用Python实现链表的分隔链表操作
链表是一种常用的数据结构,在Python中可以使用类的形式来实现链表。链表的分隔操作指将链表中的元素按照某个条件分成两个链表,比如将所有奇数节点和偶数节点分别放入两个链表中。
下面是一个示例代码,用于实现链表的分隔操作。在该代码中,链表的节点包含一个value值和一个指向下一个节点的next指针。函数split_linked_list接收一个链表的头节点作为参数,返回两个新的链表的头节点,分别包含原链表中的奇数节点和偶数节点。
class Node: def __init__(self, value, next=None): self.value = value self.next = next def split_linked_list(head): odd_head = odd_tail = None even_head = even_tail = None current = head count = 0 while current: count += 1 if count % 2 == 1: # 奇数节点 if not odd_head: odd_head = odd_tail = current else: odd_tail.next = current odd_tail = current else: # 偶数节点 if not even_head: even_head = even_tail = current else: even_tail.next = current even_tail = current current = current.next # 将尾部节点的next指针指向None if odd_tail: odd_tail.next = None if even_tail: even_tail.next = None return odd_head, even_head
我们可以使用以下代码来测试上述函数的功能:
n1 = Node('p') n2 = Node('i') n3 = Node('d') n4 = Node('a') n5 = Node('n') n6 = Node('c') n7 = Node('o') n8 = Node('d') n1.next = n2 n2.next = n3 n3.next = n4 n4.next = n5 n5.next = n6 n6.next = n7 n7.next = n8 odd_head, even_head = split_linked_list(n1) print("奇数链表:", end=" ") current = odd_head while current: print(current.value, end=" ") current = current.next print("\n偶数链表:", end=" ") current = even_head while current: print(current.value, end=" ") current = current.next
该代码的输出结果为:
奇数链表: p d n o 偶数链表: i a c d
可以看出,函数成功地将原链表中的奇数节点和偶数节点分别放入两个新的链表中。
相关文章