1,210 views
0 votes
0 votes

Consider a linked list of length n is implemented using a circular array P[0, n – 1], two variables first and last are used to point the first and last element of the list present in array respectively i.e., first = P and last = (P + x) mod n, where x is the size of linked list.

Consider the following operations:

S1: Delete kth element in linked list.

S2: Reverse the elements of linked list.

Which of the following represent the time complexity of above two operations respectively?

  • O(n), O(n)
  • O(n), O(1)
  • O(1), O(1)
  • O(1), O(n)

1 Answer

2 votes
2 votes

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  

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 :

e

(first)

d   c    b   

a

(last)

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)

Related questions

0 votes
0 votes
3 answers
1
0 votes
0 votes
1 answer
2
3 votes
3 votes
5 answers
3
srestha asked May 22, 2019
1,795 views
Consider the following function height, to which pointer to the root node of a binary tree shown below is passedNote that max(a,b) defined by #define max(a,b) (a>b)?a:b.i...