Coding Tricks

 I think I have already blogged it some where. It is very common question - next only to inversing the binary tree.  Write a function to reverse a singly linked list. Would you like to write a recursive function? No, OK, let us write a non-recursive function for this. Let us say you have first three nodes n1, n2 and n3. Now simply link n2 to n1. Next take next three nodes n2,n3 and n4 and link n3 to n2. Continue this process until you reach the end of the list. Take n1, n2 = n1->next and n3 = n2->next Set n1->next = NULL. Because this will be your last node.  Now link n2 and n1. That is set n2->next = n1. Now assign n1 = n2,  n2 = n3 and n3 = n3->next Repeat 2 steps  above until n3 = NULL. You still have one un-assigned node. Set that. n2->next = n1 Now n2 is your new head node.  That's it.  And now it is the coding time. #include<iostream> using namespace std; struct node { int n; node *next; }; class linked_list { node *h

 Here is a trick question - a data structures question for you Write a function to concat two circular linked lists. Without traversing either of them. The lists are singly linked. hint : order is not important. Let us try to understand the situation. We have two single linked circular lists. We have to join them.  One easy solution would be to traverse to the end of first list and link the last node to second list. But we are not allowed to do that.  The second possible solution could be find the previous node of head of first list - which will be last node. And then link it to second list. Again, not possible as the list is not doubly linked. Ok. Here is the solution  Let temp be the next node of head of list1 Link head of list1 to head->next of list2 Link head of list2 to temp Let us take an example. Let the two lists be  1-2-3-4-5 and 10-20-30 Now let temp=2 Assign  1->next =20.  Now we have list1 as 1-20-30-10. and back to 20 Assign 10->next=temp.   Which is 2 So now the

 Let us write Write a program to add a node to the rear of a circular linked list. Now a circular linked list has no end. That is to say, the last node in the list points back to the head of the list. So finding the last node will be slightly tricky. let temp = head while temp->next !=head temp = temp->next Once we find the last node, we append the new node here. But we must not forget to point his new node back to head. lastnode->next = newnode; newnode->next = head; The complexity is O(n).   Here is the complete program #include<iostream> using namespace std; struct node { int n; node *next; }; class linked_list { node *head; public: linked_list(int val = 0) { if(val==0) head = NULL; else{ head = new node; head->n = val; head->next = NULL; } } node* find_last_node() { if(head==NULL || head->next==head) return he

I must be missing coding. So let me write few lines of code and you tell me the output. 1) int a = 10; if(a&1) cout<<"Hello"; else cout<<"hi"; 2) for(int i=2;i<20;i++) if(i&(i-1)==0) cout<<i<<" "; 3) int i =10; cout<<(i<<3)<<" "; cout<<(i>>3)<<" "; Please do not open another window and go to online compilers.  And as I struggled a bit for this, let us see how fast you can come up with the solution.   Write a program to read two fractions and find their sum.  No, do not give me the answer in decimal. The answer should be in the form of fraction.