Solution by made easy.
But in S2 I feel it cannot be done in constant time.
Why?
Lets say we have an array :
0 |
1 |
2 |
3 |
4 |
a
(first)
|
b |
c |
d |
e
(last)
|
Now, first=0 and last=4;
Now if we reverse say first=4 and last=0
0 |
1 |
2 |
3 |
4 |
a
(last)
|
b |
c |
d |
e
(first)
|
Normally,
Deletion : first=(first+1) mod n
Insertion: last=(last+1) mod n
Now, if we delete from above, We get : e
and first=(4+1)mod 5=0
Next delete gives output a[first]=a[0]=a (WRONG)
If linked list is reversed :
First Delete output : e
Second Delete output : d
So, I feel just swaping first and last if not enough.
So,I think we can do like :
1)Keep a ptr to first node say f and a ptr to last node say l;
2)Swap contents of f and l;
3)f++ and l--
4)Repeat till f==l or f==l-1
So, time complexity =O(n)