[Python] Partition linked list around a value x : Cracking the coding Interview book

I am trying to solve an interview question such that the given linked list needs to be partition around a value say 'x'. I gave an attempt to it but not getting the desired result.

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


Thanks in advance.

Continue reading...