Dark Mode

2,473 views

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?

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

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)$

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

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

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.