Question

Please answer quickly! Thank you.

Java: Write a non-static method to be added to a class that implements a singly linked list of integers. The method is called make_partition() and takes an integer x as input. The method should modify this list by moving all the elements less than x to the front of the list, and all the elements greater than x to the back of the list. It is not the important for the elements to be kept in their original order. Note that this method should run in O(n) time.

Answer 1

The following method can be implemented using an auxillary space of O(N) copy all the elements of the of the list to an arrayList after that do the following steps

1) 1 for loop to go over the array and put all the elements which are less than x into the list from starting

2) 1 for loop after step 1 to put rest of the elements into the linked list.

Total time taken is 3N still time complexity is O(N) and space complexity is O(N)

JAVA CODE

public static make_partition(int x)
{
  
   Node cur = head;
   //create a new Array list
   List<Integer> aux = new ArrayList<>();
   //iterate over the linked list
   while(cur!=null)
   {
       //save to aux
       aux.add(cur.data);
       cur=cur.next;
   }
   cur=head;
   //go over again the array list to find element less than x
   for(int i=0;i<aux.length();++aux)
   {
       //less
       if(aux.get(i)<x)
       {
           cur.data=aux.get(i);
           cur=cur.next;
       }
      
   }
   //to place all elements greater than x in the linked list
   for(int i=0;i<aux.length();++aux)
   {
       //greater
       if(aux.get(i)>x)
       {
           cur.data=aux.get(i);
           cur=cur.next;
       }
      
   }
}