3,696 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.

## 3 Answers

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 ?

current->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;
if(head) nextP = head->next;
}
return prevP;
}


Time complexity – $\theta(n)$

Space Complexity – $O(1)$

Full working code –

#include<stdio.h>
#include<stdlib.h>

struct node {
int data;
struct node *next;
};

typedef struct node Node;

struct node *createNode(int val){
struct node *newNode = malloc(sizeof( struct node  ));
newNode->data = val;
newNode->next = NULL;
return newNode;
}

struct node* createListFromArray(int arr[], int arraySize)
{
struct node *rootNodePtr = createNode(arr[0]);
struct node *lastNodePtr = rootNodePtr;

for(int i = 1 ; i < arraySize; i++)
{
struct node *nodePtr = createNode(arr[i]);
lastNodePtr->next =nodePtr;
lastNodePtr=lastNodePtr->next;

}
return rootNodePtr;
}

void printlist(struct node *head){
printf("LIST:\n");
while(head!=NULL){
printf("%d ",head->data);
head = head->next;
}
printf("\n");
}

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;
if(head) nextP = head->next;
}
return prevP;
}

int main()
{
int arr1[] = {55,10,2,3,4,20,7,6,8,9,12,15};
struct node *head =createListFromArray(arr1, sizeof(arr1)/sizeof(int));

printlist(head);

printlist(reverse(head));

}



### 9 Comments

There must be a check of :-

if(head != NULL) before the last line of the code inside while loop. Otherwise the last iteration will become NULL pointer dereference.

@Argharupa Adhikary It is already there inside while loop.

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

@Sachin Mittal 1 Sir,

please check @Abhrajyoti00’s comment .

@Pranavpurkar Now, Sir has corrected it with the line $if(head)$

how to assume that 3 ptrs are given in the qn?

else to sort linked list in constant time w/o ptrs or with 1 ptr isnt possible

isnt it necessary to mention in the qn as some gate qns like that there in which ptrs not given and ans is not possible to do with 1 ptr etc...like that

@MANSI_SOMANI it is very clearly mentioned in question that $O(1)$ space should be used.

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

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:

16 votes
4 answers
1
5,857 views
7 votes
3 answers
2