python - 围绕值x的分区链表:破解编码面试书

我试图解决一个面试问题，这样给定的链接列表需要围绕一个值（比如“x”）进行划分。我试过了，但没有得到想要的结果。

class Node(object):
    def __init__(self, val):
        self.val = val
        self.next = None

def Partition(head, x):
    x_node = Node(x)
    x_node.next = head
    current = head
    last = x_node
    while current:
        if current.val < x_node.val:
            last = last.next
            temp_val = current.val
            current.val = last.val
            last.val = temp_val
        current = current.next
    temp_val = last.val
    last.val = x_node.val
    x_node.val = temp_val

Partition(head,3)

Input:           1->4->3->2->5->2
Actual Output:   1->2->3->4->5->3
Expected Output: 1->2->2->3->4->5

提前谢谢。

最佳答案

对于[9,2,9,3,5,8,5,10,2,1]（我在幕后神奇地转换为ll），值5的值是1,2,3,2,9,9,5,8,5,10。
问题是让所有项都小于所有项左边的值，大于或等于该值，而该值本身可以出现在右分区的任何地方注意9出现在5之前，这是意料之中的。

class Node:
    def __init__(self, data, next=None):
        self.data = data
        self.next = next

def partition(node, val):
b_n = node
head = node
right = False
while node:
    if node.data < val:
        if node == head:
            node = node.next
        else:
            head = Node(node.data, head)
            b_n.next = node.next
    else:
        right = True
        if right:
            r_e = node
    b_n = node
    node = node.next
r_e.next = None
return head

ll5 = Linked_List()
ll5.build_from_list([9,2,9,3,5,8,5,10,2,1])
ll6.head = partition(ll5.head, 5)
ll6.iterate()

.build_from_list（）和.iterate（）是我在linked_list（）类中构建的方法。