値の周りにリンクされたリストをパーティション分割するx：コーディングを割るインタビューブック

Question

インタラクティブな質問を解決しようとしています。私はその試みをしましたが、望みの結果を得られませんでした。

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]（私は舞台裏で魔法のように変換します）、私は1,2,3,2を取得しています、9,9,5,8,5,10値5の場合

質問は、値より大きいか等しいすべてのアイテムの左の値よりも小さいすべてのアイテムを持つことです。右側のパーティションのどこにでも表示されます。 Notice 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（）クラスに組み込まれているメソッドです。