*1. Under what circumstances can one delete an element from a singly linked list in constant time?
ANS.
If the list is circular and there are no references to the nodes in the list from anywhere else! Just copy the contents of the next node and delete the next node. If the list is not circular, we can delete any but the last node using this idea. In that case, mark the last node as dummy!
* 2. Given a singly linked list, determine whether it contains a loop or not.
ANS.
(a) Start reversing the list. If you reach the head, gotcha! there is a loop! But this changes the list. So, reverse the list again. (b) Maintain two pointers, initially pointing to the head. Advance one of them one node at a time. And the other one, two nodes at a time. If the latter overtakes the former at any time, there is a loop!
p1 = p2 = head;
do {
p1 = p1->next;
p2 = p2->next->next;
} while (p1 != p2);
3. Given a singly linked list, print out its contents in reverse order. Can you do it without using any extra space?
ANS.
Start reversing the list. Do this again, printing the contents.
4. Given a binary tree with nodes, print out the values in pre-order/in-order/post-order without using any extra space.
5. Reverse a singly linked list recursively. The function prototype is node * reverse (node *) ;
ANS.
node * reverse (node * n)
{
node * m ;
if (! (n && n -> next))
return n ;
m = reverse (n -> next) ;
n -> next -> next = n ;
n -> next = NULL ;
return m ;
}
6. Given a singly linked list, find the middle of the list.
HINT. Use the single and double pointer jumping. Maintain two pointers, initially pointing to the head. Advance one of them one node at a time. And the other one, two nodes at a time. When the double reaches the end, the single is in the middle. This is not asymptotically faster but seems to take less steps than going through the list twice.