# 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 = 3Output: [1,2,2,4,3,5]`

Example 2:

`Input: head = [2,1], x = 2Output: [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.

`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`