Order the array of 0 & 1

Question:

Order the list with ‘0’ first and ‘1’ second, which has ‘0’ and ‘1’ stored in irregular fashion.

Constraints:
-> Time & Space complexity to be minimal

Example:

Array: 0-1-0-1-1-0-1

Answer: 0-0-0-1-1-1-1

Answer:

-> Start with one pointer from start and another pointer from back.
-> Stop if you find ‘1’ for first pointer
-> Stop if you find ‘0’ for second pointer
-> Interchange till both the pointers are not crossed over.

Complexity:

Time: O(2N) -> O(N) , where N represents longest link list length

Example:

Array: 0-1-0-1

Answer: 0-0-1-1

Tracing:

Step 1:

-> Let Pointer 1 points to head of array
-> Let Pointer 2 points to tail of array

Step 2:

-> Pointer 1 will stop at node 2 as it has '1'

Step 3:

-> Pointer 2 will stop at node 3 as it has '0'

Step 4:

-> Interchange the values of node 2 & 3 with 0 & 1 respectively

Step 5:

-> Pointer 1 crosses over Pointer 2. Stop

Answer:

0-0-1-1