in DS edited by
2,414 views
4 votes
4 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 edited by
by
2.4k views

3 Answers

3 votes
3 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

4 Comments

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

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” https://cwe.mitre.org/data/definitions/476.html

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. 

0
0
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.

https://stackoverflow.com/questions/9076923/how-can-i-reverse-a-linked-list

1 vote
1 vote

We can use three-pointers.

ListNode* reverseList(ListNode* head) {
        ListNode* prev=NULL;
        ListNode* curr=head;
        ListNode* nex;
        while(curr!=NULL){
            nex=curr->next;
            curr->next=prev;
            prev=curr;
            curr=nex;
        }
        head=prev;
        return head;
    }

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

So, the answer is A.

Answer:

Related questions