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

Data-Structures

Question 8
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?

A
B
C
D
It is not possible to reverse a singly linked list in O (1) space.
Question 8 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)
Correct Answer: A
Question 8 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)

Leave a Reply

Your email address will not be published. Required fields are marked *