in DS retagged ago by
6 votes
6 votes

Consider the problem of reversing a singly linked list. To take an example, given the linked list below,

the reversed linked list should look like

Which one of the following statements is $\text{TRUE}$ about the time complexity of algorithms that solve the above problem in $O(1)$ space?

  1. The best algorithm for the problem takes $\theta(n)$ time in the worst case.
  2. The best algorithm for the problem takes $\theta(n \log n)$ time in the worst case.
  3. The best algorithm for the problem takes $\theta(n^{2})$ time in the worst case.
  4. It is not possible to reverse a singly linked list in $O(1)$ space.
in DS retagged ago by

3 Answers

4 votes
4 votes
Best answer

Answer A

Suppose you are given a linkedlist like this – 

And you want to convert this to as follows-

Which means, you just want to change pointer of node that is pointed by current.

Which line would do same ?

currennt->next = previous

That is all.

Now we just need to shift our pointers – prev, current and next.

Which is also easy

prev = current
current = next
next = current->next // or next = current->next

Now lets combine all lines together – 

    struct node * reverse( struct node * head )
        struct node * prevP = NULL;
        struct node * nextP = head->next;

        while(head != NULL) {
            head->next = prevP;
            prevP = head;
            head = nextP;
            nextP = head->next;
        return prevP;

Time complexity – $\theta(n)$

Space Complexity – $O(1)$

edited by


Can anyone explain how is constant space used here ?
No additional datastructure is used for storing the result . Original linked list’s linked is reserved thus space complexity is O(1).

Yes @Argharupa Adhikary your observation is correct.

@raja11sep No. @Argharupa Adhikary is talking about the fact that :-  

the code says 

head = nextP;

Now this head might point to an invalid location. After this when the line 


nextP = head->next;

will be executed there will be a crash which she termed as “NULL pointer de-reference”

Hence, there must be a check of if(head!=NULL) just before that line as:-

head = nextP;

if(head!=NULL)  //This line needs to be added

head = nextP;

@Sachin Mittal 1 Sir, there needs to be an edit. 

3 votes
3 votes

The correct answer is option A.

Reversing a linked list only requires one traversal of entire linked list of N elements and Change the appropriate Pointers.

The Time complexity is $\Theta (n)$.

one can go through the link for some understanding if finds it difficult.

1 vote
1 vote

We can use three-pointers.

ListNode* reverseList(ListNode* head) {
        ListNode* prev=NULL;
        ListNode* curr=head;
        ListNode* nex;
        return head;

The above Algorithm works in $\Theta (n)$ time in worst case.

So, the answer is A.