Move All Zeroes To the Start Geeks For Geeks

Problem Link:

https://practice.geeksforgeeks.org/problems/move-all-zeros-to-the-front-of-the-linked-list/1#

(It is also the problem of the day for 2 April 2022.)

Solution 1:

class GfG{

    public Node moveZeroes(Node head){

        Node temp1=new Node(-1);//zero linked list

        Node temp2=new Node(-1);//non-zero linked list

        Node temp3=temp1;

        Node temp4=temp2;

        Node temp5=head;

        while(temp5!=null){

            if(temp5.data==0){

                temp1.next=new Node(0);

                temp1=temp1.next;

            }

            else{

                temp2.next=new Node(temp5.data);

                temp2=temp2.next;

            }

            temp5=temp5.next;

        }

        temp1.next=temp4.next;

        return temp3.next;

    }

}

Total Test Cases:100

Time Complexity:O(N)[GFG Time:0.3/1.5]

Space Complexity: O(N)Given is a Linked list 

Auxiliary Space: O(N)[2 Linked list is created of different sizes]

Approach Used:

1. Here we will traverse the given linked list and see whether the value is 0 or not.

2. If the value is 0 then we will store it in the new linked list(temp1) otherwise in temp2.

3. Later we will merge both linked lists.

temp1 is a new linked list of zero values.

temp2 is the new linked list of non-zero elements.

temp3 is pointing to the head of temp1 linked list

temp4 is pointing to the head of temp2 linked list.

temp5 is pointing to the head of the given linked list.

When we will traverse the given liked list by temp5 we will see whether the element is 0 or not.

If the element has a value of data as 0 then we will add it to the temp1 list and move ahead. Similarly, if it's not zero then we will add it in temp2 ad move ahead.

In last we will see out temp1 will be:

-1 -> 0 -> 0 -> 0

and temp2

-1 -> 2 -> 3 ->4 

Now we will merge the second list into the first list but we should know two things

1. Whom to point

2. From where to point

Whom to point.

temp2 will be pointing at the last value in it ie 4 so we can't point to temp2.

We need ahead of the temp2 linked list which will be temp4

Fro where to point.

We know temp1 will be pointing at the last value means 0 so we directly connect it to temp4

so temp1.next=temp4

But one problem will be there as -1 of starting of temp4 will come in between of linked list.

-1 ->0 ->0 -> 0-> -1 ->2->3->4

To rectify this we will modify preovius connection to

temp1.next=temp4.next

and s temp4=-1 and temp4.next=2 

Moreover, to remove starting node with a -1 value we will point to temp3.next as

temp3=-1

temp3.next=0

So last, we will return temp3.next as temp3 is pointing to temp1 ie the newly created linked list.

 

=========================================================================

Solution 2:

Node temp=head;

        int count=0;

        Node temp1=new Node(-1);

        Node temp3=temp1;

        while(temp.next!=null){

            if(temp.next.data==0){

                Node a=temp.next.next;

                temp.next=a;

                //temp.next.next=null;

                count++;

            }

            else{

                temp=temp.next;

            }

        }

        Node temp2=head;

        while(count!=0){

            temp1.next=new Node(0);

            count--;

            temp1=temp1.next;

        }

        while(temp2!=null){

            temp1.next=new Node(temp2.data);

            temp2=temp2.next;

            temp1=temp1.next;

        }

        return temp3.next;

Total Test Cases:100

Time Complexity:O(N)[GFG Time:0.2/1.5]

Space Complexity: O(N)[Given is a Linked list] 

Auxiliary Space: O(N)[1 Linked list is created]

Approach Used:

It's similar to the previous approach but with slight modifications

Here we will count the number of nodes having zero value and store them in the count variable, and simultaneously if the value is non zero then we will remove that node from the linked list.

Later we will make a new linked list and run it till count!=0 and add it with zeroes.

Now we have one linked list with all 0 values and another with non-zero values so now we will merge both the linked list and merge them into one.

Here the point to observe is that if the given linked list is

0 2 3 0 4 0 5 1

so now by logic, we will get output as 

count=2 and 

list(modified)=0 2 3 4 5

It is so because we will start traversal from the head and we will not see the value present at the head of the linked list due to which if it is 0 then it will be merged at the time of merging and if it's non zero then also there is no problem because it is index value or head value and it will always come at first.

Later we will return the merger list.

In the above code, we return temp3.next as temp3 will be -1 and temp3.next will be 0.

The difference in complexities between the two approaches:

1. In the first two linked lists are created, while in the second one linked list is created impacting low auxiliary space in the second approach.

2. In the first approach linked list remains the same while in the second it got modified and its size reduces. 

In case 1. when the given list will have all 0 nodes.

First approach: one linked list with full-fledged 0 nodes

Second approach: Linked list creation and modification in the given list as its size will be reduced to 1(head node only with 0 value will remain at last).

In case 2. When the list is having all nonzero entries

First approach: One list will be created with full-fledged non-zero nodes.

Second approach: count remains 0 and modification in the list remains untouched.

The difference between using two additional ArrayList and the linked lists is that 

We need to define a specific ArrayList here while the linked list is defined well and moreover we will utilize that structure of the linked list and modify the list according to your resource.

"Thanks For Reading.😇"

"Share Further To Increase Knowledge Treasure.😊"