Partition Linked List

Given a linked list and a target value T, partition it such that all nodes less than T are listed before the nodes larger than or equal to target value T. The original relative order of the nodes in each of the two partitions should be preserved.

Examples

L = 2 -> 4 -> 3 -> 5 -> 1 -> null, T = 3, is partitioned to 2 -> 1 -> 4 -> 3 -> 5 -> null

class Solution(object):
  def partition(self, head, target):
    head1 = ListNode(0)
    head2 = ListNode(0)
    tmp = head
    p1 = head1
    p2 = head2
    while tmp:
      if tmp.val < target:
        p1.next = tmp
        tmp = tmp.next
        p1 = p1.next
        p1.next = None
      else:
        p2.next = tmp
        tmp = tmp.next
        p2 = p2.next
        p2.next = None
    p1.next = head2.next
    head = head1.next
    return head