Interview Question Software Engineer / Developers
Country: -
The question is to find the middle node in "one" traversal, right? That is the difference. The later approach requires two traversals obviously.
hey..could u say wht a traversal mean fr u?? i think in the two pointer approach too v r traversing it twice.the difference is when v finish the traversal wit fast pointer ..v get the middile node immediately wit the help of the second traversal wit the slow pointer....but if u at look at it carefully u do the same amount of work in both the methods...not any more or less..i think the two pointer approach has some benefits related to CACHING..could somebody make tht part clear if possible??
The two pointer approach is better.
1. In the 2 pointer approach no of times, we check for NULL condition is always n/2, to check whether the fast pointer has reached end), whereas in other approach it is n.
2. In 2 pointer approach the middle is reached automatically when fast pointer reaches end of the list whereas in other approach, after finding the length, again we need to check each time if it has reached the middle (for i=1; i <= (n/2); i++),
here i <= (n/2), is an extra computation, which is not required in the first approach.
My comments for two pointer approach against single pointer:
Consider a case when we use single pointer, calculate the length, and then some other part of the application simply appends few nodes in the list (this is realistic, right?)
So when we move ahead and try to traverse to the point (calculatedLength/2), what we are getting is not the correct solution. In worst case, we can also get NPE if all the nodes from rear end to mid have been deleted before we identified middle element.
On the contrary, two pointer approach always gives results based on Linked lists current state.
hi..happy to receive a comment from u..i accept the two pointer approach will work fine in that case..but what if the linked list is not modified??.(i.e)no nodes are appended after calculating the length..what advantage does the two pointer method has in that case?? why i am emphasizing is because everybody goes with the two pointer approach but i don't find any advantage in it....
Hey,
We can use skip list in this case:
1) While traversing each node in the Linked List make a skip list of the odd numbered nodes. Time: O(n) Space: O(n/2)
2) Now when you reach the end of the list divide the legnth by 2 and add 1 to get the middle element index.
3) Search for the index in the skip list O(logn) time.
So, Overall Time Complexity of the algorithm would be :
O(n)(1 traversal) + O(logn)(Searching Skip list) = O(n)
Space Complexity : O(n/2)
Please reply if this is inefficient....
If extra memory is allowed ,use hash map. While traversing the list add nodes to hash map, where key will be position of node and value will be address of the node.As length is always odd so return hash[(n+1)/2].
But clearly it needs two traversals..rite??..having two pointers and moving them in different speed doesn't make any difference in the number of traversals we make..rite??
It does not require two traversal. Interivewer clearly mentioned that length is alwasy odd. So that is the catch here.
We cand to it with a single traversal. So keep an extra storage array of node address.
1. Start traversing list and push the alternate node on the array. Keep a count of nodes you are pushing in array.
2. Once you reach at the end of list. Divide the count by 2 and look for that index in your array of nodes and that is the middle node. (take care of indexing starting at 0)
For example
1->2->3->4->5->Null
array will have arr[0]=Node 1
arr[1]=Node 3
arr[2]=Node 5
Total count is 3 so 3/2 gives 1 and that is the middle element which is arr[1].
Dumb question: What will you initialize the array to if don't know the number of alternate nodes?
only store nodes with even position, as we need to return hash[(n+1)/2] which is even,that way we dont need to store all nodes.
Node* FindMiddleNoad(Node* head)
{
Node* MidNode=head;
while(head->Next!=null && head->Next->Next!=null)
{
MidNode=Midnode->Next;
head=head->Next->Next;
}
return MidNode;
}
Yes the solution I gave is wrong and will always give the third node from the last.
In the above solution you provided is using two node pointers and two traversals are happening.
If the question does not limit abt space and time, then array or hashing is correct. But we will loose the property of linked lists.
I dont think any such solution exists.
Hey,
What about implementing a Skip List...
1) While Traversing the Linked List, build a level 2 linked list which will contains odd numbered nodes.
Takes 1 traversal, O(n) Time, O(n/2) Space
2) At the end of list divide the length by 2 and add 1 to get the middle element number.
3) Search for node in the skip list O(logn) time.
Overall Complexity : O(n) + O(logn) = O(n)
Two pointers approach does not have any limitation to linked list length. It also does not need to compute number division (n/2). This could save a little bit of CPU clock (if you care that much).
- Anonymous October 04, 2011But main advantage here is that two pointers approach can be used with "infinite" length, whereas the counting approach can only use with linked list that has length within Integer range (2^32).