2,414 views

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.

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;

}
return prevP;
}


Time complexity – $\theta(n)$

Space Complexity – $O(1)$

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

the code says

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

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:-

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

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.

We can use three-pointers.

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

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

1
2
1 vote
3