Consider a singly linked list containing n elements in which A is the address of the
Consider a singly linked list containing n elements in which A is the address of the
starting node of the linked list. If we first convert the linked list to an array, then sort the
array elements, and then create a new linked list from the elements of the sorted array,
what is the number of operations required to traverse the linked list and store its data
values in an additional array before applying sorting?
Show answerHide answer
Correct answer: (C) O(n)
Explanation
Copying the data needs a single pass through the list, visiting each of the n nodes once, so it takes O(n) operations. The later sorting step is what needs O(n log n).