GATE 2022
October 16, 2023Higher-Education-and-Politics
October 16, 2023GATE 2022
Question 15
|
Consider the problem of reversing a singly linked list. To take an example, given the linked list below,
![](https://solutionsadda.in/wp-content/uploads/2022/03/16-300x83.png)
Which one of the following statements is TRUE about the time complexity of algorithms that solve the above problem in O (1) space?
![](https://solutionsadda.in/wp-content/uploads/2022/03/16-300x83.png)
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