围绕值x对链表进行分区:破解编码面试书

Question

我正在尝试解决一个面试问题，以便给定的链表需要围绕一个值"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

提前谢谢。

Answer 1

对于 [9,2,9,3,5,8,5,10,2,1]（我在幕后神奇地将其转换为 ll），我得到值 1,2,3,2,9,9,5,8,5,10 的值为 5。

问题是让所有项目小于大于或等于该值的所有项目左侧的值，其中值本身可以出现在右侧分区中的任何位置。通知 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（） 类中的方法。