Bissoy.com
Doctors Medicines MCQs Q&A

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 TRUE about the time complexity of algorithms that solve the above problem in O(1) space?

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 TRUE about the time complexity of algorithms that solve the above problem in O(1) space? Correct Answer The best algorithm for the problem takes <span style="">θ(n)</span> time in the worst case. 

The correct answer is option 1.

Concept:

Single linked list:

A single linked list is a sort of unidirectional linked list that may only be traversed in one way, from head to final node (tail). A node is a name for each element in a linked list. A single node includes data as well as a pointer to the next node, which aids in the list's structure.

Explanation:

The time complexity of reversing a linked list is linear in time i.e O(n) where n is the size of the linked list.

Algorithm:

  1. Initialize three-pointers prev as NULL, curr as head and next as NULL.
  2. Iterate through the linked list. In loop, do following. 
    // Before changing next of current, store next node 
    next = curr->next
    // Now change next of current This is where actual reversing happens 
    curr->next = prev 
    // Move prev and curr one step forward 
    prev = curr 
    curr = next

Analysis:

  • Initialize three-pointers prev as NULL, curr as head and next as NULL.
  • Iterate through the linked list,
  • And check whether there are any nodes in the linked list then move forward to the nodes by changing the nodes allocations.
  •  Before changing the next of current, store the next node.
  • Now change next of current This is where actual reversing happens with curr->next = prev.
  • Move prev and curr one step forward with, prev = curr  and curr = next.

So we need to traverse the whole linked list in the given linked list it takes n time to travel all elements in the linked list. So the best algorithm for the problem takes θ(n) time in the worst case. 

Hence the correct answer is the best algorithm for the problem that takes θ(n) time in the worst case. 

Related Questions

Fact 1: All dogs like to run.
Fact 2: Some dogs like to swim.
Fact 3: Some dogs look like their masters.

If the first three statements are facts, which of the following statements must also be a fact?
I: All dogs who like to swim look like their masters.
II: Dogs who like to swim also like to run.
III: Dogs who like to run do not look like their masters.
Match List I with List II List I List II (A) Greedy Best-First Search (I) Space complexity is O(d) where d = depth of the deepest optimal solution (B) A* (II) Incomplete even if the search space is finite. (C) Recursive Best-First Search (III) Optimal if optimal solution is reachable: otherwise, returns the best reachable optimal solution. (D) SMA* (IV) Computation and space complexity is too high.   Choose the correct answer from the options given below:
Consider a singly linked list of the form where F is a pointer to the first element in the linked list and L is the pointer to the last element in the list. The time of which of the following operations depends on the length of the list?
Given below are some famous algorithms and some algorithm design paradigms Algorithms Design Paradigm  1. Dijkstra's shortest path algorithms  (a) Greedy design  2. Floyd-Warshall's all-pair-shortest path algorithms  (b) Divide and conquer  3. Kruskal's minimum spanning tree algorithm  (c) Dynamic programming  4. Merge Sort algorithm     Which of the following correspondence is correct?
Read the given statements and conclusions carefully. Assuming that the information given in the statements is true, even if it appears to be at variance with commonly known facts, decide which of the given conclusions logically follow(s) from the statements. Statements: All Matter is Space. Some Mass is Matter. Conclusions: A. All Mass is Space. B. Some Mass is Space. C. Some Space is Mass. D. All Space is Mass. E. All Matter is Mass.
Study information given and select valid conclusion/s from the given statements based on it. In a joint family the number of members who take only coffee is equal to the half the number of members who take tea and the number of persons who take only tea is equal to the half the number of persons who take coffee. Statements: a. The total number of persons who take either coffee or tea or both is thrice the number of persons who take only coffee or only tea. b. The total number of persons who take only coffee and those who take only tea is twice the number of persons who take both coffee and tea.
The following are the conditions for selecting list of a suitable candidates to be called for interview after the written test for the recruitment is conducted/organized for management - level persons for a multi - national company. For providing accounting services and sales the candidate must (a) be holding a graduation in basic science with 65% or above or B.E. degree with 55% and above marks (b) have passed the written test with 70% or above marks (c) the age must be in the group 25 to 30 years as on 1/4/18 (d) have experience in an accounting firms for three years and diploma in accounting with 60% or above marks (e)  be presently drawing CTC of 6 Lakhs per annum and above In case the applicant who satisfies all other terms above except 1) at (a) above, then be referred as Junior Accountant 2) at (d) & (e) above then be referred as Trainee - Accountant Satisfying all the above with experience of 5 years then the referred as senior-Accountant Satisfying all the above criteria (a - e) with CA/ICWA/MBA (Finance) then be referred as manager (Accounts) Read all the above information and answer the following question Praveen has done his Masters in physics. He has no experience in accounting neither diploma. He is ready to be on training for accounting after joining. For which position he may be referred
The following are the conditions for selecting a list of suitable candidates to be called for interview after the written test for the recruitment is conducted/ organized for management-level persons for a multi-national company. For providing accounting services and sales the candidate must (a) beholding graduation in basic science with 65% or above or B.E. degree with 55% and above marks (b) have passed the written test with 70% or above marks (c) the age must be in the group 25 to 30 years as on 1/4/18 (d) have experience in an accounting firm for three years and a diploma in accounting with 60% or above marks e) be presently drawing CTC 6 lakhs per annum and above In case the applicant who satisfies all other terms above except 1) at (a) above, then be referred to as Junior Accountant 2) at (d) & (e) above then be referred to as Trainee-Accountant Satisfying all the above with experience of 5 years then be referred to as senior-Accountant Satisfying all the above criteria (a-e) with CA/ICWA/MBA (Finance) then be referred to as manager (Accounts) Read all the above information and answer the following question   Praveen has done his Masters in physics. He has no experience in accounting neither diploma. He is ready to be on training for accounting after joining. For which position he may be referred.
In the following question, five statements are given followed by four conclusions I, II, III and IV. You have to consider the given statements to be true even, if they seem to be at variance with commonly known facts. Read all the conclusions and decide which of the following logically follows from the given statements disregarding the commonly known facts. Statements: Some Blue are Color. All Color are Sky. No Rocket is Sky. All Rocket are Space. No Space is Color. Conclusions: I. Some Sky being Space is a possibility. II. Some Blue are Sky. III. Some Color being Rocket is a possibility. IV. Some Blue being Rocket, Space, Sky and Color is a possibility.
The following are the conditions for selecting list of a suitable candidates to be called for interview after the written test for the recruitment is conducted/ organized for management-level persons of a multi-national company. For providing accounting services and sales the candidates must (a) be holding a graduation in basic science with 65% or above or B. E degree with 55% and above marks (b) have passed the written test with 70% or above marks (c) the age must be in the group 25 to 30 years as on 1/4/18 (d) have experience in an accounting firms for three years and diploma in accounting with 60% or above marks (e) be presently drawing CTC of 6 Lakhs per annum and above In case the applicant who satisfies all other terms above except 1) at (a) above, then be referred as Junior Accountant 2) at (d) & (e) above then be referred as Trainee-Accountant Satisfying all the above with experience of 5 years then be referred as senior-Accountant Satisfying all the above criteria (a-e) with CA/ ICWA / MBA (Finance) then be refereed as manager (Accounts) Read all the above information and answer the following question Shravani has passed H. SC with 72% of marks. She has done diploma in accountancy with 62% of marks. She was working with an organization in the field of accounting in the field of accounting from 4 years and was drawing CTC of 6.5 Lakhs presently. She is 28yrs as on July 2018. She may referred for the position of: