retagged by
9,064 views
19 votes
19 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.
retagged by

4 Answers

Best answer
22 votes
22 votes

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 by
14 votes
14 votes

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

2 votes
2 votes

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:

Related questions

40 votes
40 votes
3 answers
1
34 votes
34 votes
6 answers
2