Python中链表的划分为小于、等于、大于某个值的三个部分操作

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

def partition(head: ListNode, x: int) -> ListNode:
    # 定义三个指针
    small = small_head = ListNode(0)
    equal = equal_head = ListNode(0)
    great = great_head = ListNode(0)

    # 遍历原链表，将节点插入到对应的链表中
    while head:
        if head.val < x:
            small.next = head
            small = small.next
        elif head.val == x:
            equal.next = head
            equal = equal.next
        else:
            great.next = head
            great = great.next
        head = head.next

    # 将三个链表连接起来
    small.next = equal_head.next if equal_head.next else great_head.next
    equal.next = great_head.next

    # 返回新连接好的链表头
    return small_head.next 

head = ListNode("p")
head.next = ListNode("i")
head.next.next = ListNode("d")
head.next.next.next = ListNode("a")
head.next.next.next.next = ListNode("n")
head.next.next.next.next.next = ListNode("c")
head.next.next.next.next.next.next = ListNode("o")
head.next.next.next.next.next.next.next = ListNode("d")
head.next.next.next.next.next.next.next.next = ListNode(".")
head.next.next.next.next.next.next.next.next.next = ListNode("c")
head.next.next.next.next.next.next.next.next.next.next = ListNode("o")
head.next.next.next.next.next.next.next.next.next.next.next = ListNode("m")

new_head = partition(head, "n")

while new_head:
    print(new_head.val)
    new_head = new_head.next

i
d
a
c
o
p
n
c
o
d
.
c
o
m