Reverse a singly linked list

 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.

1. Take n1, n2 = n1->next and n3 = n2->next
2. Set n1->next = NULL. Because this will be your last node. 
   
1. Now link n2 and n1. That is set n2->next = n1.
2. Now assign n1 = n2,  n2 = n3 and n3 = n3->next
3. Repeat 2 steps  above until n3 = NULL.
4. You still have one un-assigned node. Set that. n2->next = n1
5. 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 *head;  
  public:  
    linked_list(int val = 0)  
    {  
      if(val!=0){  
      head = new node;  
      head->n = val;  
      head->next = NULL;  
      }else{  
       head = NULL;  
     }  
     }  
     node* find_last_node()  
     {  
       node* temp = head;  
       while(temp!=NULL && temp->next!=NULL)  
         temp = temp->next;  
       return temp;  
     }  
     void append(int val)  
    {  
      node *nd = new node;  
      nd->n = val;  
      nd->next = NULL;  
      node *last_node = find_last_node();  
      if(last_node!=NULL)   
           last_node->next = nd;  
      else  
           head = nd;  
    }  
    void display()  
    {  
       node* temp = head;  
       while(temp)  
       {  
         cout<<temp->n<<" ";  
         temp = temp->next;  
       }  
    }  
      void reverse_list()  
      {  
         node* l1,*l2,*l3;  
        l1 = head;  
         l2 = l1->next;         
        l3 = l2->next;        
         l1->next = NULL;    
        while(l3!=NULL)  
         {  
           l2->next = l1;    
              l1 = l2;  
           l2 = l3;  
           l3 = l3->next;  
         }    
         l2->next = l1;  
         head=l2;  
       }  
 };  
 int main()  
 {  
    linked_list lst;  
    for(int i = 0;i<5;i++)  
    {  
      int n;  
      cout<<"Number:";  
      cin>>n;  
      lst.append(n);  
    }  
    cout<<"The linked list is ";  
    lst.display();  
    lst.reverse_list();  
    cout<<"Now the list is";  
    lst.display();  
 }