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

Dark Mode

3,696 views

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

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

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)); }

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.

1

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.