3,593 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 ?

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;

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

printf("LIST:\n");
}
printf("\n");
}

struct node * reverse( struct node * head )
{
struct node * prevP = NULL;
struct node * nextP = head->next;

}
return prevP;
}

int main()
{
int arr1[] = {55,10,2,3,4,20,7,6,8,9,12,15};

}



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.

@Sachin Mittal 1 Sir,

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

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.