# Partition List

Given the `head`

of a linked list and a value `x`

, partition it such that all nodes **less than** `x`

come before nodes **greater than or equal** to `x`

.

You should **preserve** the original relative order of the nodes in each of the two partitions.

**Example 1:**

**Input:** head = [1,4,3,2,5,2], x = 3

**Output:** [1,2,2,4,3,5]

**Example 2:**

**Input:** head = [2,1], x = 2

**Output:** [1,2]

**Constraints:**

- The number of nodes in the list is in the range
`[0, 200]`

. `-100 <= Node.val <= 100`

`-200 <= x <= 200`

Solution

Approach 1:

The problem may look trickier at the first glance . But if you think for a second this is just a simple problem. The intuition behind this problem is that, you basically traverse the linked list and store all the elements less than the value x in an array in an order ,as is found in the linked list. At the same time store all the elements greater than or equal to the value x , into another array as in the order in the linked list.

Then finally iterate through the array and then replace all the linked list values as in the order they are in the array. Which is what you essentially need.

`def partition(self, head, x):`

small,large=[],[]

temp=head

while(temp!=None):

if(temp.val<x):

small.append(temp.val)

else:

large.append(temp.val)

temp=temp.next

small=small+large

temp=head

index=0

while(temp!=None):

temp.val=small[index]

temp=temp.next

index+=1

return head

Time: O(n)

Space: O(n)

Approach 2:

The next approach is taking advantage of the linked list property and there by reducing the space complexity to O(1).

Here we create 2 nodes small and large which will be two seperate linked list that will hold all the values less than and greater than or equal to respectively.

First we traverse the linked list , and if the value of current node is found to be less than x , then we extend the next pointer of the small linked list to the current node, else we extend the next pointer of the large linked list to the current node .After finished traversing the given linked list, we find that both of the small and large linked list will basically hold the values, as in the same order as is in the given linked list . Now the only task that remains is to extend the next pointer of the small linked list to the head of the large linked list , thus join both of them. Finally return the head of the small linked list ,which is the required answer.

`def partition(self, head, x):`

small=ListNode(0)

large=ListNode(0)

small_pointer=small

large_pointer=large

while(head!=None):

if(head.val<x):

small.next=head

small=head

else:

large.next=head

large=head

head=head.next

large.next=None

small.next=large_pointer.next

return small_pointer.next

Time: O(n)

Space: O(1)