###### GATE 2022

October 16, 2023###### Higher-Education-and-Politics

October 16, 2023# GATE 2022

Question 15 |

Consider the problem of reversing a singly linked list. To take an example, given the linked list below,

Which one of the following statements is TRUE about the time complexity of algorithms that solve the above problem in O (1) space?

Which one of the following statements is TRUE about the time complexity of algorithms that solve the above problem in O (1) space?

It is not possible to reverse a singly linked list in O (1) space. |

Question 15 Explanation:

/* Link list node */

struct Node {

int data;

struct Node* next;

{

this->data = data;

next = NULL;

}

};

struct LinkedList {

Node* head;

LinkedList() { head = NULL; }

/* Function to reverse the linked list */

void reverse()

{

// Initialize current, previous and

// next pointers

Node* current = head;

Node *prev = NULL, *next = NULL;

while (current != NULL) {

// Store next

next = current->next;

// Reverse current node’s pointer

current->next = prev;

// Move pointers one position ahead.

prev = current;

current = next;

}

head = prev;

}

For the above algorithm :

Time Complexity: O(n)

Space Complexity: O(1)

struct Node {

int data;

struct Node* next;

{

this->data = data;

next = NULL;

}

};

struct LinkedList {

Node* head;

LinkedList() { head = NULL; }

/* Function to reverse the linked list */

void reverse()

{

// Initialize current, previous and

// next pointers

Node* current = head;

Node *prev = NULL, *next = NULL;

while (current != NULL) {

// Store next

next = current->next;

// Reverse current node’s pointer

current->next = prev;

// Move pointers one position ahead.

prev = current;

current = next;

}

head = prev;

}

For the above algorithm :

Time Complexity: O(n)

Space Complexity: O(1)

Correct Answer: A

Question 15 Explanation:

/* Link list node */

struct Node {

int data;

struct Node* next;

{

this->data = data;

next = NULL;

}

};

struct LinkedList {

Node* head;

LinkedList() { head = NULL; }

/* Function to reverse the linked list */

void reverse()

{

// Initialize current, previous and

// next pointers

Node* current = head;

Node *prev = NULL, *next = NULL;

while (current != NULL) {

// Store next

next = current->next;

// Reverse current node’s pointer

current->next = prev;

// Move pointers one position ahead.

prev = current;

current = next;

}

head = prev;

}

For the above algorithm :

Time Complexity: O(n)

Space Complexity: O(1)

struct Node {

int data;

struct Node* next;

{

this->data = data;

next = NULL;

}

};

struct LinkedList {

Node* head;

LinkedList() { head = NULL; }

/* Function to reverse the linked list */

void reverse()

{

// Initialize current, previous and

// next pointers

Node* current = head;

Node *prev = NULL, *next = NULL;

while (current != NULL) {

// Store next

next = current->next;

// Reverse current node’s pointer

current->next = prev;

// Move pointers one position ahead.

prev = current;

current = next;

}

head = prev;

}

For the above algorithm :

Time Complexity: O(n)

Space Complexity: O(1)

Subscribe

Login

0 Comments