rengasami21
BAN USER@mayank.hey : You are right, I can eliminate next pointer totally here. Thats an additional variable. But how to eliminate the other one? I tried a lot for one pointer and no Additional DS. At the max I can reach here. Can you help me?
- rengasami21 November 07, 2013This algo will fail at <space><space>ab<space>a. This is because we have skipped spaces until we reach a and we found that a matches exactly with k's value which is a and the flag becomes one. Now since the i index reaches n/2 it will break the loop and the function returns true. So doing it till n/2 will make it fail. We have to iterate full.
- rengasami21 November 04, 2013List* reverse_list(List* head)
{
List* current = head;
List* result = NULL;
while(current != NULL)
{
List* next = current->next;
current->next = result;
result = current;
current = next;
}
return result;
}
This code looks good to me but it uses two pointers (considering result as a pointer) and it doesnt use any additional storage.
I found it in one of the blogspot site.
It takes O(n). Is this correct?
List* reverse_list(List* head)
{
List* current = head;
List* result = NULL;
while(current != NULL)
{
List* next = current->next;
current->next = result;
result = current;
current = next;
}
return result;
}
I got this solution from one of the blogspot sites. Unfortunately I am not able to paste link here.
I think, this makes some sense. But if you consider result as a separate pointer storage. This uses two pointers but without any additional storage.
I feel takes o(n)
Is this correct?
How it will be O(1)? I think recursive search on a binary tree makes it O(logN)? Can somebody help me in understanding?
- rengasami21 September 18, 2013Hi Bill, if three nodes fall under the same level how will you determine its parents? This might happen at the second level of the tree.
- rengasami21 September 06, 2013
if index is 0 it cannot have any other to compare with. So OR is correct relationship. If we use and it will try to obtain an array element with -1 as index which is wrong
- rengasami21 June 01, 2014Great answer Brandy