/*****************
1. Given a Linked List of nodes, say, A* head, write a function to check if another given node,
A* b, is in that list.
bool check(A* head, A* b)
*******************************/
#include <iostream>
using namespace std;


class A{
public:
  char c;
  A* next;

  A(char x='a'){
    c=x;
    next=NULL;
  }
 
  A* add_to_head(A* p){
    p->next=this;
    return p;
  }


  void display(){
    A* p=this;
    while(p!= NULL){
      cout<<"c = "<<p->c<<endl;
      p=p->next;
    }
    cout<<"-----------"<<endl<<endl;
  }

};

bool check(A* head,A* b);
int main(){
  A a1('T'),a2('r'),a3('C'),a4('J'),a5('k'), a6('p'),a7('&'), a8('8'),a9('%');
  A* head=&a1;
  head->display();
  head=head->add_to_head(&a2);
  head->display();
  head=head->add_to_head(&a4);
  head->display();
  head=head->add_to_head(&a7);
  head->display();
  head=head->add_to_head(&a5);
  head->display();
  head=head->add_to_head(&a3);
  head->display();
  if (check(head, &a7)){
    cout<<"a7 is in the list\n";
  }else{
    cout<<"a7 is NOT in the list\n";
  }

  if (check(head, &a6)){
    cout<<"a6 is in the list\n";
  }else{
    cout<<"a6 is NOT in the list\n";
  }
  if (check(head, &a1)){
    cout<<"a1 is in the list\n";
  }else{
    cout<<"a1 is NOT in the list\n";
  }

  if (check(head, &a9)){
    cout<<"a9 is in the list\n";
  }else{
    cout<<"a9 is NOT in the list\n";
  }


}

bool check(A* head,A* b){
  A* temp=head;
  if(temp==b){
    return true;
  }
  else{
    while (temp->next != NULL){
      temp=temp->next;
      if(temp==b){
	return true;
	break;
      }
    }
  }
  return false;
}