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)