in DS retagged by
3,541 views
9 votes
9 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?

  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.
in DS retagged by
by
3.5k views

3 Answers

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

   
}

 

edited ago by

4 Comments

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
1

@Sachin Mittal 1 Sir,

please check @Abhrajyoti00’s comment .

1
1

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

0
0
3 votes
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
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.