python - 围绕一个值 x : Cracking the coding Interview book 划分链表

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](我在幕后神奇地将其转换为 all)，我得到 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() 类中构建的方法。