1. Describe an algorithm to find the middle node (or element) of a singly linked
ID: 3553873 • Letter: 1
Question
1. Describe an algorithm to find the middle node (or element) of a singly linked list in one pass. i.e. your algorithm will traverse
the list starting from the head of the list and ending at the last node with the answer. You can use temporary variable in
your algorithm. What would be the run time complexity and space complexity of your algorithm representing in BIG-O notation.
1.) b. Estimate the run time complexity of the following: for( int I = 1 ; I < n; I++ ) sum ++;
for( int j = 1; j < I ; j =j *2 ) sum ++;
1.) c. Estimate the run time complexity of the following:
for( int I = 1 ; I < n; I++ )
for( int j = 1; j < I ; j =j *2 )
sum++;
Explanation / Answer
1.
(a) Take two node objects, say A and B. Let the length of the list be X.
(b) Move A by two nodes and B by 1 node until A reaches the end of the list.
(c) Till the end, A has travelled X nodes. But, since B was traversing through the list with half the velocity of A, so, B has travelled only X / 2 node.
(d) Print the data at B. This will give you the value of middle node in one loop only.
1. (b).
Here, variable I runs (n - 1) times, and j runs (i/2) times in for each iteration of i.
So, complexity will be theta(n^2)
1. (c).
Same as 1. (b).
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.