Linked List Questions and C++ Notes

Question - How do you find there is a loop in a linkedlist

• Have two pointers to parse the list.
• One is slow pointer and another is fast
• Slow = Head->next
• Fast = Head->next->next
• Increment Slow by one position and Fast by 2 Positons. When the address and value matches then a loop exists

Question – Two Linked lists are merged by mistake, How do you fix it.
Assume it is

A->B->C->D->E
F->T->D->E

• Parse the list with two headers H1 and H2
• Store all the elements of two lists in two separate stack
• Now Stack would appear like A,B,C,D,E and F,T,D,E
• Now Pop one element from both stack until you find last match common element
• Here last match common element is D, When you move beyond D the stack values differs, The list got merged at D Node

I did not put C code right now but I hope approach and description is sufficient to visualize it to some extent :)
Linked List - Notes

• Dynamic Allocation gives flexibility
• Use as much or as little space as needed
• Addition - constant time
• Searching - propotional to n
• Deletion - propotional to n

C++ Notes
Runtime Polymorphism - Function Overloading

#include<iostream.h>

  //FUNTION OVERRIDING

  class Base

  {

    public:

    virtual void print()=0;

  };

  class child : Base

  {

    public:

    void print()

    {

     cout<<"In Child Class";

    }

  };

  int main(void)

  {

     child c;

     c.print();

     return 1;

   }

Working and Tested code in http://codepad.org/

Another interesting example from link

#include<iostream.h>
class Base { 
public:     
void NonVirtual() 
{         
 cout<<"Base NonVirtual called.\n";     
}     
virtual void Virtual() 
{         
 cout<<"Base Virtual called.\n";     
} 
//virtual void purevirtual()=0;

}; 

class Derived : public Base 
{ 
public:     
void NonVirtual() 
{         
 cout<<"Derived NonVirtual called.\n";     
}     
void Virtual() 
{         
 cout<<"Derived Virtual called.\n";     
} 

/*void purevirtual()
{
       cout<<"pure virtual \n";
}*/
};  

int main() 
{     
 Base* bBase = new Base();
        bBase->NonVirtual();
        bBase->Virtual();
 Base* bDerived = new Derived();      
 bDerived->NonVirtual();     
 bDerived->Virtual(); 
   //     bDerived->purevirtual();
} 

With pure virtual function uncommented you would not be able to instantiate base class. With Above commented lines output listed below

Base NonVirtual called. Base Virtual called. Base NonVirtual called. Derived Virtual called.

Copy Constructor link
Copy constructor is- a constructor function with the same name as the class
- used to make deep copy of objects.
Happy Reading!!