GATE CSE 2022 | Question: 5

Question

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?

• A. The best algorithm for the problem takes $\theta(n)$ time in the worst case.
• B. The best algorithm for the problem takes $\theta(n \log n)$ time in the worst case.
• C. The best algorithm for the problem takes $\theta(n^{2})$ time in the worst case.
• D. It is not possible to reverse a singly linked list in $O(1)$ space.

Answer 1

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

   
}

 

Comments

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

Answer 2

Clearly it is $\theta(n)$. You can see the visualization in the below GIF.

Answer 3

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

Answer 4

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.