1. Write functions for inserting and deleting elements to a linked list.

A node can be inserted to the list either to the end, after last node, or at the begining or some where in the middle.

Append node - add a node to end - requires you to traverse the list to find last node and then add new node after last node. So it has a time complexity of O(n)

Insert at begining - adds a node before head. As there is no need to traverse the list, this has complexity of O(1). This function sets newnode->next to head and then sets head as newnode.

For deletion of any node, you again need to find previous node and link previous node to next node of node to be deleted. So deletion has complexity of O(n)

struct node
{
   int n;
   struct node* next;
};
typedef struct node* NODEPTR; 
NODEPTR delete_node(NODEPTR head, int num)
 {
    NODEPTR dnode,prevnode,temp;    
    prevnode=head;
    if(head->n==num)/*delete first*/
    {
        temp = head; 
        head = head->next; 
        free(temp);
        return head;
    }
    temp=head->next;
    while(temp!=NULL)
    {
       if(temp->n==num)/*node found*/
       {
          prevnode->next = temp->next;/*link prev and next nodes*/
          free(temp);
          return head;
       }
       prevnode = temp;
       temp = temp->next;
    }
    printf("Node not found");
    return NULL;
}
NODEPTR insert_before_head(NODEPTR head, NODEPTR newnode)  
 {  
    newnode->next = head;
    head = newnode;
    return head;
 } 

 NODEPTR append_node(NODEPTR head, NODEPTR newnode)  
 {  
    NODEPTR temp = head;
    if(temp==NULL)
      return newnode;
    while(temp->next !=NULL)
	temp = temp->next;
    temp->next = newnode;
    return head;  
 } 
NODEPTR create_node(int num)
{
   NODEPTR temp = (NODEPTR)malloc(sizeof(struct node));
   temp->n = num;
   temp->next = NULL;
   return temp;
} 
void display_list(NODEPTR nd)
{
   printf("Now list is");
   while(nd!=NULL)
   {
       printf("%d   ",nd->n);
       nd = nd->next;
   }
}
/****function call examples****/
int main()
{
     NODEPTR head =NULL;
     int n=11;
     struct node *newnode = create_node(n);
     head = append_node(head,newnode); 
     int m = 11;
     head = delete_node(head,m);
     m=98;
     head = insert_before_head(head,m); 
     display_list(head);
}

#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;
            }
     }
     node* find_previous_node(node *nd)
     {
            node* temp = head;
            while(temp)
           {
                if(temp->next == nd)
                    return temp;
                temp = temp->next;
            }
            return NULL;
   }
   
     void delete_node(int n)
     {
          node *temp = find_node(n);
          if(temp==NULL)
            cout<<"The node is not found";
         else{
         if(temp==head)
           {
                 head = head->next;
                 delete temp;
             cout<<"Node deleted successfully";
           }
          else if(temp!=NULL)
          {
               node *prev_node = find_previous_node(temp);
               if(prev_node!=NULL)
               {
                      prev_node->next = temp->next;
                      delete temp;
                  cout<<"Node deleted successfully";
                }
          }  
      }
   }
    node * find_node(int n)
    {
          node *temp = head;
          while(temp && temp->n !=n)
              temp = temp->next;
          
           return temp;
     }
};
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();
     int m;
     cout<<"Enter a node to be deleted:";
     cin>>m;
     lst.delete_node(m);
     cout<<"Now the list is";
     lst.display();
}

2. Write a function to delete a node N from a doubly linked list. Assume that there are nodes on either sides of node to be deleted.

When we are deleting a node from a DLL, we should link its previous node to its next node. So the code is very simple.
delnode->prev->next = delnode->next
delnode->next->prev = delnode->prev

In this example, it has been mentioned that the node is middle node. But in general case, we have to verify that the previous node and nextnode of delnode are not NULL. Also we should modify head, if delnode is head. In such a case, function must return the changed head node.

 void delete_node(NODEPTR head, NODEPTR delnode)
{
     if(delnode==head)/*deleting first node 
	    head = head->next;        
     if(delnode->prev)
        delnode->prev->next = delnode->next;
      if(delnode->next)
        delnode->next->prev = delnode->prev;
        free(delnode);
       
}

3. Write a function to merge two singly linked lists.

We should traverse till the end of first list - list1.

Next we have to link this last node of list1 to head of list2.
last1->next = head2;

Complexity - O(n1)

 void merge_nodes(NODEPTR l1, NODEPTR l2)
 {
     /* move to the end of list1*/
     while(l1!=NULL && l1->next !=NULL)
        l1 = l1->next;
  /**link last node of list1 to l2***/
     if(l1!=NULL)  
        l1->next = l2;
 }

4. Write a function to find average of elements in a linked list

To find average of elements you need to traverse the list and add elements together. You also need to count the number of nodes.

Then calculate
average= sum/count

 float average(NODEPTR h1)
 {
     int sum = 0;
     int count =0;
     while(h1)
     {
        sum+=h1->n;
        h1 = h1->next;
        count++;
     }
     return (float)sum/count;
}

5. Write a program to replace all the occurrences of a given value in a linked list by another value.

While traversing, if we find that node has search value s, we should replace node->n with replace value r

 #include<stdio.h>  
#include<stdlib.h>
 struct node  
 {  
   int n;  
   struct node *next;   
 };  
 typedef struct node * NODEPTR;   
/*sv is search value, rv is replace value*/
void replace_nodes(NODEPTR h1, int sv,int rv)
{
     while(h1)
     {
         if(h1->n == sv)
            h1->n = rv;
        h1 = h1 ->next;
     }
}   
 NODEPTR create_node(int value)  
 {  
   NODEPTR temp = (NODEPTR) malloc(sizeof(struct node));  
    temp->next = NULL;  
   temp->n = value;  
   return temp;  
 }  

 NODEPTR append_node(NODEPTR head, NODEPTR newnode)  
 {  
    NODEPTR temp = head;
    if(temp==NULL)
      return newnode;
    while(temp->next !=NULL)
	temp = temp->next;
    temp->next = newnode;
    return head;  
 } 
 
 void display_nodes(NODEPTR head)  
 {  
   NODEPTR temp = head;//redundant 
   while (temp!= NULL)  
   {  
     printf("%d====>",temp->n);  
     temp = temp->next;  
   }  
   printf("\n");
 }  

 int main()  
 {  
     NODEPTR head1;   
     int numnodes1,i;  
     int s,r;
     //initialize head  
     head1=  NULL;  
     printf("Number of nodes in list1 = ");  
     scanf("%d",&numnodes1);       
     for(i = 0;i<numnodes1;i++)  
     {  
       int value;  
       NODEPTR newnode;  
       printf("node value=");  
       scanf("%d",&value);  
       newnode = create_node(value);  
       head1 = append_node(head1,newnode);      
     }  
     printf("The linked list   now is ");  
     display_nodes(head1); 
     printf("Search value");
     scanf("%d",&s);
     printf("Replace with");
     scanf("%d",&r);
     replace_nodes(head1,s,r);
     printf("The linked list after replacing is ");  
     display_nodes(head1); 
 }

#include<iostream>
using namespace std;
struct node
{
   int n;
   node *next;
};
class linked_list
{
    node *head;
  public:
      linked_list(int val = 0)
      {
         head = new node;
         head->n = val;
         head->next = 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;
      }
      void display()
      {
            node* temp = head;
            while(temp)
           {
                cout<<temp->n<<" ";
                temp = temp->next;
            }
     }
     void replace_values(int old_val,int new_val)
     {
          node *temp = head;
          while(temp)
	  {
               if(temp->n==old_val)
                   temp->n = new_val;
               temp = temp->next;
           }
  }  
};
int main()
{
     linked_list lst(10);
     for(int i = 0;i<10;i++)
     {
          int n;
          cout<<"Number:";
          cin>>n;
          lst.append(n);
     }
     cout<<"The linked list is ";
     lst.display();
     int m,n;
     cout<<"Enter the value to be replaced and new value";
     cin>>m>>n;
     lst.replace_values(m,n);
     cout<<"Now the list is";
     lst.display();
}

6. Write a function to insert a value into a ordered (sorted) linked list.

In this case, we must find a node N whose key value is just greater than new node. Now new node has to be inserted before this node N. You also need to maintain prevnode while traversing

while nd!=NULL and nd->val <newnode->val
previousnode = nd
move to next node
link previous node to newnode
link newnode to nd

This function can even be used to create a sorted list. Because if each element is inserted using this function, then the list will be automatically sorted.

#include<stdio.h>  
#include<stdlib.h>
 struct node  
 {  
   int n;  
   struct node *next;   
 };  
 typedef struct node * NODEPTR;  
 NODEPTR create_node(int value);    
 void display_nodes(NODEPTR head);  
 
NODEPTR insert_sorted(NODEPTR head, NODEPTR newnode)
 {
    NODEPTR prevnode = NULL,l1 = head;
    while(l1!=NULL)
   {
      if(l1->n >newnode->n)
           break;/*we found location*/
      prevnode = l1;
      l1 = l1->next;
    }
    if(prevnode==NULL)/* insert at beginning*/
    {
       newnode->next = head;
       head = newnode;
     }
    else/*insert before l1*/
   {
       newnode->next = l1;
       prevnode->next = newnode;               
    }
    return head;
  }
 /*driver program*/
int main()
{
     NODEPTR head = NULL;
     while(1)
    {
       int n;
       printf("Enter a value to be inserted (-1 to quit");
       scanf("%d",&n);
       if(n==-1)
          break;
       NODEPTR newnode = create_node(n);
       head = insert_sorted(head,newnode);
     }
     display_nodes(head);
}

  
create_node() and display_nodes() functions are not shown here

#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;
	  }
       }
      
      void display()
      {
            node* temp = head;
            while(temp)
           {
                cout<<temp->n<<" ";
                temp = temp->next;
            }
     }
     void  insert_value(int m)
     {
          node * temp = head;
	        node *prev = NULL;
          
          while(temp && temp->n < m)
          {
                prev = temp;
                temp = temp->next;
           }
	   /*create a node  nn*/
          node *nn = new node;
          nn->n = m;
           nn->next = NULL;
   
	        if(prev!=NULL)
           {
	      	   prev->next = nn;
		         nn->next = temp;
	         }else/*insert at begining of list*/
            {
		        nn->next = head;
		        head = nn;
            }
        }     
};
int main()
{
     linked_list lst;
     for(int i = 0;i<10;i++)
     {
          int n;
          cout<<"Number:";
          cin>>n;
          lst.insert_value(n);
          /*nodes are inserted in ascending order*/
     }
     cout<<"The linked list is ";
     lst.display();
     
}

7. Write a function to display all values in a singly linked list.

To display a linked list, you need to start from head and traverse all the nodes until you reach NULL.

 void display_nodes(struct node *nd)
 {
     while(nd!=NULL)
     {
          printf("%d\n",nd->val);
          nd = nd->next;
      }
}
/***calling this***/
int main()
{
  -------
  display_nodes(head);
----
}

8. Write functions to insert a node at the front and rear of a circular linked list

In a circular list, traversal should take into account the fact that there is no NULL in the list. Because last node of the list points back to head.

So Traversal should continue till you reach head again.

If we write a traversal loop like

  for(temp=head;temp!=NULL; temp=temp->next)

the loop will be infinite as there is no NULL in this list.

Traversal can be done using a do while loop

temp=head
do

visit the node temp
move to next node

while temp is not head

This way we are ensuring that loop is terminated when we come across head for the second time.

For inserting a node to front (or rear) of a circular singly linked list, you need to just add the new node before head.

find lastnode of list
newnode->next = head;
lastnode->next = newnode;
head = newnode;

To find the last node, you need to traverse the list. So time complexity is O(n).

But if the order is unimportant to you, you can add the node "after head", so that the time complexity is O(1)

second = head->next
head->next = newnode;
newnode->next = second;

 #include<stdio.h>  
#include<stdlib.h>
 struct node  
 {  
   int n;  
   struct node *next;   
 };  
 typedef struct node * NODEPTR;  
 
 NODEPTR create_node(int value)  
 {  
   NODEPTR temp = (NODEPTR) malloc(sizeof(struct node));  
    temp->next = NULL;  
   temp->n = value;  
   return temp;  
 } 
 NODEPTR insert_front(NODEPTR head, NODEPTR newnode)  
 {  /*complexity is O(n)*/
    NODEPTR temp = head;
    if(head==NULL)
    {
        newnode->next = newnode;
        return newnode;
    }
    while(temp->next !=head)
	temp = temp->next;
    newnode->next = head;
    temp->next = newnode;
    head = newnode;
    return head;  
 }

 void insert_after_head(NODEPTR head,NODEPTR newnode)
{/*complextiy is O(1)*/
     newnode->next = head->next;
     head->next = newnode;
}
 void display_nodes(NODEPTR head)  
 {  
   NODEPTR temp = head; 
   if(head==NULL)
	return;
   do  
   {  
     printf("%d---->",temp->n);  
     temp = temp->next;  
   } while(temp!=head);
   printf("\n");
 }   
 int main()  
 {  
     NODEPTR head; 
     int numnodes,i;  
     //initialize head  
     head =  NULL;  
     printf("Number of nodes = ");  
     scanf("%d",&numnodes);  
     for(i = 0;i<numnodes;i++)  
     {  
       int value;  
       NODEPTR newnode;  
       printf("node value=");  
       scanf("%d",&value);  
       newnode = create_node(value);  
       head = insert_front(head,newnode);      
     }  
     printf("The linked list now is "); 
     display_nodes(head);   
     insert_after_head(head,create_node(111));
     printf("The linked list now is ");  
     display_nodes(head);   
 }

#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 head;
         node* temp = head;
         do{
		      temp = temp->next;
        }while(temp->next!=head);
        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;
				nd->next = head;
          }
         else if(head==NULL)/*list empty*/
 			{
              head = nd;
	      	  nd->next = nd;
         }
		else{/*only one node*/
				head->next = nd;
				nd->next = head;
        }	
      }
      void display()
      {
            node* temp = head;
            do
           {
                cout<<temp->n<<" ";
                temp = temp->next;
            }while(temp!=head);
     } 
};
int main()
{
     linked_list lst;
     for(int i = 0;i<10;i++)
     {
          int n;
          cout<<"Number:";
          cin>>n;
          lst.append(n);
     } 
     cout<<"The linked list is ";
     lst.display();
}

9. Write a function to add a node after the node with given value in a linked list. e.g. insert a new node with value 100 after a node with value 10.

This is quite simple We need to find the node with given value. Then link the node to newnode. And link newnode to next node of this node

Find m which is node with value
newnode->next = m->next
m->next = newnode

You do not have to worry about boundary condition because we are inserting the node after given node. Even if the node is head, the function will not modify head.

 #include<stdio.h>  
#include<stdlib.h>
 struct node  
 {  
   int n;  
   struct node *next;   
 };  
 typedef struct node * NODEPTR;  

void insert_after( NODEPTR newnode,NODEPTR n1)
{
        //add the node after n1
        NODEPTR n2 = n1->next;
        n1->next = newnode;        
        newnode->next = n2;        
} 
 NODEPTR create_node(int value)  
 {  
   NODEPTR temp = (NODEPTR) malloc(sizeof(struct node));  
    temp->next = NULL;  
   temp->n = value;  
   return temp;  
 } 
 

 NODEPTR append_node(NODEPTR head, NODEPTR newnode)  
 {  
    NODEPTR temp = head;
    if(temp==NULL)
      return newnode;
    while(temp->next !=NULL)
	temp = temp->next;
    temp->next = newnode;
    return head;  
 } 
 void display_nodes(NODEPTR head)  
 {  
   NODEPTR temp = head;//redundant 
   while (temp!= NULL)  
   {  
     printf("%d====>",temp->n);  
     temp = temp->next;  
   }  
   printf("\n");
 } 

 NODEPTR find_node(NODEPTR temp, int val)
 {
      while(temp)
        {
           if(temp->n==val)
                 return temp;
           temp = temp->next;
        }
     return NULL;//node not found
} 

 int main()  
 {  
     NODEPTR head;  
     NODEPTR newnode,dnode;  
     int numnodes,i;
     int m,n;  
     //initialize head  
     head =  NULL;  
     printf("Number of nodes = ");  
     scanf("%d",&numnodes);  
     
     for(i = 0;i<numnodes;i++)  
     {  
       int value;  
       NODEPTR newnode;  
       printf("node value=");  
       scanf("%d",&value);  
       newnode = create_node(value);  
       head = append_node(head,newnode);      
     }  
     printf("The linked list now is ");  
     display_nodes(head); 
     printf("Enter the value for new node:");
     scanf("%d",&m);
     printf("This should be inserted after which node :");
     scanf("%d",&n);
     dnode = find_node(head,n);
     if(dnode==NULL)
         printf("The value is not found in the list");
     else
        {
           newnode = create_node(m);
           insert_after(newnode,dnode);
           printf("Node successfully inserted\nNow the list is:");
           display_nodes(head);
       } 
 }

#include<iostream>
using namespace std;
struct node
{
   int n;
   node *next;
};
class linked_list
{
    node *head;
  public:
      linked_list(int val = 0)
      {
         head = new node;
         head->n = val;
         head->next = 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;
      }
      void display()
      {
            node* temp = head;
            while(temp)
           {
                cout<<temp->n<<" ";
                temp = temp->next;
            }
     }
     node * find_node(int n)
    {
          node *temp = head;
          while(temp && temp->n !=n)
              temp = temp->next;
           return temp;
     }
   void insert_after(node *nd,int val)
   {
         node *nn = new node;
         nn->n = val;
         nn->next = NULL;
         /*insert node*/
      nn->next = nd->next;
        nd->next = nn;
    }   
};
int main()
{
     linked_list lst(10);
     for(int i = 0;i<4;i++)
     {
          int n;
          cout<<"Number:";
          cin>>n;
          lst.append(n);
     }
     cout<<"The linked list is ";
     lst.display();
     int m,n;
     cout<<"New node?=";
     cin>>m;
     cout<<"Insert after ?:";
     cin>>n;
     node *temp = lst.find_node(n);
     if(temp!=NULL)
     {
         lst.insert_after(temp,m);
      }
      else
          cout<<"The value "<<n<<" in not found in the list";
     cout<<"Now the list is";
     lst.display();
}

10. What are the advantages of doubly linked list over a singly linked list?

Allows traversal of nodes in both directions

Insertion and deletion of nodes is easy when compared to singly linked list, because in singly linked list you need to find previous node for these operations. In DLL, the each node has a link to previous node so that insert and delete operation can use this link.

But keep in mind that because of extra link in each node, size of doubly linked list is larger.

11. For a singly linked list with integer data, write a function to search for a value.

Searching in a linked list is always be done using sequential search. We need to traverse the list until search value is found.

If the list is sorted, then searching can be terminated when we find a value larger than search value.

First function searches in an unsorted list and second function searches for a value in a sorted list. Both these function return the node which contain search value if found. If not found, they return NULL.

Time complexity of search operation- O(n)

 NODEPTR find_node(NODEPTR temp, int val)
 {/*function to search in an unsorted list*/
      while(temp)
        {
           if(temp->n==val)
                 return temp;/*we found value*/
           temp = temp->next;
        }
     return NULL;/*node not found*/
}

NODEPTR find_node_sorted(NODEPTR temp, int val)
{/*search in sorted list*/
     while(temp!=NULL && temp->n <val)
           temp = temp->next;
     if(temp->n==val)
       return temp;
     return NULL;
}

12. Write a program to concatenate two singly linked circular lists without traversing either of them.

The easiest way to do this is in a singly linked list is
a) Point head1 to l22 where l22 is second node of list2
b) Point head2 to l12 where l12 is second node of list1

So if circular list1 is A---B---C
and circular list2 is P---Q---R

after concatenation list will be A---Q---R---P---B---C--

Sample output
Number of nodes of list1 = 3
node value=10
node value=20
node value=30
Number of nodes of list2 = 4
node value=1
node value=2
node value=3
node value=4
Now the merged list is 10---->2---->3---->4---->1---->20---->30---->

 #include<stdio.h>  
#include<stdlib.h>
 struct node  
 {  
   int n;  
   struct node *next;   
 };  
 typedef struct node * NODEPTR;  
 
void concat(NODEPTR head1,NODEPTR head2)
{ 
     NODEPTR nx = head1->next;
     head1->next = head2->next;
     head2->next= nx;
}
     
 NODEPTR create_node(int value)  
 {  
   NODEPTR temp = (NODEPTR) malloc(sizeof(struct node));  
    temp->next = NULL;  
   temp->n = value;  
   return temp;  
 } 

 NODEPTR insert_rear(NODEPTR head, NODEPTR newnode)  
 {  
    NODEPTR temp = head;
    if(head==NULL)
      {
	     newnode->next = newnode;
        return newnode;
      }
    while(temp->next !=head)
	temp = temp->next;
    temp->next = newnode;
    newnode->next = head;
    return head;  
 } 
 
  
 void display_nodes(NODEPTR head)  
 {  
   NODEPTR temp = head; 
   if(head==NULL)
	return;
   do  
   {  
     printf("%d---->",temp->n);  
     temp = temp->next;  
   } while(temp!=head);
   printf("\n");
 }   

 int main()  
 {  
     NODEPTR head1,head2; 
     int numnodes1,num2,i;  
     //initialize head  
     head1 = head2=  NULL;  
     printf("Number of nodes of list1 = ");  
     scanf("%d",&numnodes1);  
     for(i = 0;i<numnodes1;i++)  
     {  
       int value;  
       NODEPTR newnode;  
       printf("node value=");  
       scanf("%d",&value);  
       newnode = create_node(value);  
       head1 = insert_rear(head1,newnode);      
     }  
     printf("Number of nodes of list2 = ");  
     scanf("%d",&num2);  
     for(i = 0;i<num2;i++)  
     {  
       int value;  
       NODEPTR newnode;  
       printf("node value=");  
       scanf("%d",&value);  
       newnode = create_node(value);  
       head2 = insert_rear(head2,newnode);      
     }  
     concat(head1,head2);
     printf("Now the merged list is ");
     display_nodes(head1);
 }

#include<iostream>
using namespace std;
struct node
{
   int n;
   node *next;
};
class circular_list
{
    node *head;
  public:
      circular_list(int val = 0)
      {
         if(val==0)
        head = NULL;
        else{
            head = new node;
            head->n = val;
            head->next = NULL;
        }
      }
      node*get_head() 
      {
	   return head;
      }
       
       node* find_last_node()
       {
           if(head==NULL || head->next==head)
                return head;
            node* temp = head;
           while(temp->next!=head){
               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;
             nd->next = head;
          }
         else if(head==NULL)/*list empty*/
        {
              head = nd;
              nd->next = nd;
         }
        else{/*only one node*/
              head->next = nd;
              nd->next = head;
         }    
      }
      void display()
      {
            node* temp = head;
            do
           {
                cout<<temp->n<<" ";
                temp = temp->next;
            }while(temp!=head);
     } 
};
void concat_cir_lists(circular_list& lst1,circular_list& lst2)
{
     node * temp = lst1.get_head()->next;
     lst1.get_head()->next = lst2.get_head()->next;
     lst1.get_head()->next = temp;
}
int main()
{
     circular_list lst;
     cout<<"Enter values for first list terminated by -1";
     for(int i = 0;i<10;i++)
     {
          int n;
          cout<<"Number:";
          cin>>n;
	  if(n==-1)
              break;
          lst.append(n);
     } 
     cout<<"First linked list is ";
     circular_list lst2;
    cout<<"Enter values for second list terminated by -1";
     for(int i = 0;i<10;i++)
     {
          int n;
          cout<<"Number:";
          cin>>n;
	  if(n==-1)
              break;
          lst2.append(n);
     } 
     lst2.display();  
     concat_cir_lists(lst,lst2);
     lst.display(); 
}

13. Write a program a delete a node from a circular linked list.

The delete operation involves linking previous node to the next node of N where N is the node to be deleted.

As in other operations, we need to remember that last node does not point to NULL in circular lists.

If the first node viz head node is to be deleted, we need to link last node of list to second node. One method of doing this would be find the last node using traversal, then link last node to second node. Free first node and mark second node as head.

The optimized method to delete head node is
move the data of second node to head node
mark second node for deletion
link first node to third node
delete second node

What happens if we have only one node and it has to be deleted? The list will become empty - head must be made NULL. But how do we check this condition? if head->next = head, then there is only one node in the list.

   #include<stdio.h>  
#include<stdlib.h>
 struct node  
 {  
   int n;  
   struct node *next;   
 };  
 typedef struct node * NODEPTR;  
 
 NODEPTR create_node(int value)  
 {  
   NODEPTR temp = (NODEPTR) malloc(sizeof(struct node));  
    temp->next = NULL;  
   temp->n = value;  
   return temp;  
 } 
 NODEPTR insert_rear(NODEPTR head, NODEPTR newnode)  
 {  
    NODEPTR temp = head;
    if(head==NULL)
      {
	newnode->next = newnode;
        return newnode;
      }
    while(temp->next !=head)
	temp = temp->next;
    temp->next = newnode;
    newnode->next = head;
    return head;  
 } 
 void display_nodes(NODEPTR head)  
 {  
   NODEPTR temp = head; 
   if(head==NULL)
	return;
   do  
   {  
     printf("%d---->",temp->n);  
     temp = temp->next;  
   } while(temp!=head);
   printf("\n");
 } 
  NODEPTR delete_node(NODEPTR head, int num)
 {
     NODEPTR temp = head;
     NODEPTR prev = NULL;
     int found = 0;
     /*search the node*/
     if(temp->n==num)
       found=1;
     else
     while(  1)
     {          
         if(temp->n==num)
         {
            found = 1;
            break;
         }
         prev= temp;
         temp = temp->next;
         if(temp==head)
            break;
      }
      if(!found)
         printf("That value is not present in the list ...");
      else
        {
           if(prev!=NULL)
            {
               prev->next = temp->next;
               free(temp);
            }
            else
            {/*first node to be deleted*/
               if(head->next!=head)             
              {	 /*we have more than one node*/
              	 head->n = head->next->n;
                 /*copy the data of second node*/
                 temp = head->next;
                 head->next = head->next->next;
	         /*delete 2nd node*/
                 free(temp);
              }
              else/*we have only one node*/
                 {
                     head = NULL;
                     free(temp);
                  }               
            }
	}
       return head;
}          

 int main()  
 {  
     NODEPTR head; 
     int numnodes,i;  
     //initialize head  
     head =  NULL;  
     printf("Number of nodes = ");  
     scanf("%d",&numnodes);  
     for(i = 0;i<numnodes;i++)  
     {  
       int value;  
       NODEPTR newnode;  
       printf("node value=");  
       scanf("%d",&value);  
       newnode = create_node(value);  
       head = insert_rear(head,newnode);      
     }  
     printf("The linked list now is "); 
     display_nodes(head);  
     printf("Enter node to be deleted:");
     scanf("%d",&i);
     head = delete_node(head,i);
     printf("The linked list now is ");  
     display_nodes(head);   
 }

#include<iostream>
using namespace std;
struct node
{
   int n;
   node *next;
};
class circular_list
{
    node *head;
  public:
      circular_list(int val = 0)
      {
         if(val==0)
        head = NULL;
        else{
            head = new node;
            head->n = val;
            head->next = NULL;
      }
}
      node*get_head() 
      {
	   return head;
      }
       
       node* find_last_node()
       {
           if(head==NULL || head->next==head)
                return head;
            node* temp = head;
           while(temp->next!=head){
               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;
             nd->next = head;
          }
         else if(head==NULL)/*list empty*/
        {
              head = nd;
              nd->next = nd;
         }
        else{/*only one node*/
              head->next = nd;
              nd->next = head;
         }    
      }
      void display()
      {
            node* temp = head;
            do
           {
                cout<<temp->n<<" ";
                temp = temp->next;
            }while(temp!=head);
     } 
     node* find_node(int val)
     {
          node* temp = head;
          do
	  {
		if(temp->n == val)
		    return temp;
                temp = temp->next;
            }while (temp!=head);
            return NULL;
        }
        node *find_previous_node(node *nd)
        {
	      node*temp = head;
              do
              {
		  if(temp->next==nd)
                          return temp;
                  temp = temp->next;
                }while(temp!=head);
                return NULL;
       }
         bool delete_node(int val)
         {
		node *temp = find_node(val);
                if(temp!=NULL)
                {
		     node *pre_node = find_previous_node(temp);
                     if(pre_node!=NULL)
                     {
                           pre_node->next = temp->next;
			   if(temp==head)
                                head  = head->next;
                           delete temp;
                           return true;                 
                     } 
               }else
                {
			cout<<"value not found";
                }      
                return false;              
               }
};
 
int main()
{
     circular_list lst;
     cout<<"Enter values for first list terminated by -1";
     for(int i = 0;i<10;i++)
     {
          int n;
          cout<<"Number:";
          cin>>n;
	  if(n==-1)
              break;
          lst.append(n);
     } 
     cout<<"First linked list is ";      
     lst.display(); 
     cout<<"Enter value to be deleted:";
     int num;
     cin>>num;
     if(lst.delete_node(num))
           cout<<"node deleted";
      else
           cout<<"node not deleted";
      cout<<"now the list is ";
      lst.display();     
}

14. Explain how do you represent polynomials using a linked list. Write a function to add two polynomials represented as singly linked lists

A polynomial can be stored as a linked list with the help of structures with three members - exponent , co-efficient and link to next node. One structure represents one term in the polynomial.

5x^3 ------> 4x^2 ------->10

12x^2 ----> 3x ------>18

e.g.

In the first polynomial list, there are 3 nodes. First node has exponent as 3, coeff as 5. Second node has exponent as 2 and coeff as 4. Last node has exponent as 0 and coeff as 10. First node is the head.

The structure to represent such a term in polynomial term can be as below.

struct node
{
int exponent;
float coeff;
struct node *next;
};

To add two polynomials, we need to traverse both of them parallely and copy the smaller terms if exponents are unequal and add co-efficients when exponents are equal.

Known issue : This program fails if the terms of polynomial are not entered in descending order.

#include<stdio.h>  
#include<stdlib.h>
 struct node  
 {  
   int coeff;
   int exponent;
   struct node *next;   
 };  
 typedef struct node * NODEPTR;   
NODEPTR create_node(int exp,int coeff);
NODEPTR append_node(NODEPTR head,NODEPTR newnode);
NODEPTR add_polynomials(NODEPTR head1, NODEPTR head2)
 {
    NODEPTR s = NULL;/*result polynomial*/
    while(head1!=NULL && head2!=NULL)
    {
          if(head1->exponent > head2->exponent)
         {/*add term from first polynomial and move to next */
             NODEPTR temp = create_node(head1->coeff,head1->exponent);
             s = append_node(s,temp);
             head1 = head1->next;
          }else if(head2->exponent > head1->exponent)
         {/*add term from second polynomail and move to next*/
             NODEPTR temp = create_node(head2->coeff,head2->exponent);
             s = append_node(s,temp);
             head2 = head2->next;
         }else
         {
             /*exponents are equal. Add co-effs. Move to next for both*/
              int c = head1->coeff+head2->coeff;
              NODEPTR temp = create_node(c,head2->exponent);
              s = append_node(s,temp);
              head2 = head2->next;	
              head1 = head1->next;
         }
    }
    while(head1!=NULL)
    {/*add remaining terms*/
	NODEPTR temp = create_node(head1->coeff,head1->exponent);
	s = append_node(s,temp);
	head1 = head1->next;
     }
    while(head2!=NULL)
    {/*add remaining terms*/
	NODEPTR temp = create_node(head2->coeff,head2->exponent);
	s = append_node(s,temp);
	head2= head2->next;
     }
     return s;
}
 
 NODEPTR create_node(int c1,int e1)  
 {  
   NODEPTR temp = (NODEPTR) malloc(sizeof(struct node));  
    temp->next = NULL;  
   temp->coeff = c1; 
   temp->exponent = e1; 
   return temp;  
 } 

 NODEPTR append_node(NODEPTR head, NODEPTR newnode)  
 {  
    NODEPTR temp = head;
    if(temp==NULL)
      return newnode;
    while(temp->next !=NULL)
	temp = temp->next;
    temp->next = newnode;
    newnode->next = NULL;
    return head;  
 } 
 
 void display_nodes(NODEPTR head)  
 {  
   NODEPTR temp = head;
   int i=0;
   while (temp!= NULL)  
   {  
     if(i++>0)
       printf("+");
     if(temp->exponent>0)
        printf("%dX^%d",temp->coeff,temp->exponent);
     else
        printf("%d ",temp->coeff); 
     temp = temp->next;  
   }  
   printf("\n");
 } 
 
 
 int main()  
 {  
     NODEPTR head,head2; 
     NODEPTR sumlist = NULL; 
     NODEPTR newnode,dnode;  
     int numnodes,i;  
     //initialize head  
     head =  head2 = NULL;  
     printf("Number of terms in first polynomial = ");  
     scanf("%d",&numnodes);  
     
     for(i = 0;i<numnodes;i++)  
     {  
       int c1,e1;  
       NODEPTR newnode;  
       printf("node coeff and node exponent=");  
       scanf("%d %d",&c1,&e1);  
       newnode = create_node(c1,e1);  
       head = append_node(head,newnode);      
     }  
     printf("The first polynomial is ");
     display_nodes(head);
     printf("Number of terms in second polynomial = ");  
     scanf("%d",&numnodes);  
     
     for(i = 0;i<numnodes;i++)  
     {  
       int c1,e1;  
       NODEPTR newnode;  
       printf("node coeff and node exponent=");  
       scanf("%d %d",&c1,&e1);  
       newnode = create_node(c1,e1);  
       head2 = append_node(head2,newnode);      
     }  
     printf("The second polynomial is ");
     display_nodes(head2);
     printf("The addition of two polynomials is ");  
     //display_nodes(head2); 
   
     sumlist = add_polynomials(head,head2);
     display_nodes(sumlist);           
 }

#include
using namespace std;
struct node
{
   int exp;
   int coeff;
   node *next;
};
class poly_list
{
    node *head;
  public:
      poly_list(int e = 0,float c=0.0f)
      {
         if(e!=0){
         head = new node;
         head->exp = e;
         head->coeff=c;
         head->next = NULL;
	}else{
            head = NULL;
        }
       }
       node *get_head()
       {
            return head;
        }
       node* find_last_node()
       {
            node* temp = head;
            while(temp!=NULL && temp->next!=NULL)
                temp = temp->next;
            return temp;
       }
       void append(int e,float c)
      {
         node *nd = create_node(e,c);         
         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<coeff<<"x^"<exp<<"+";
                temp = temp->next;
            }
     }
     node* create_node(int e,float c)
     {
 		node *newnode = new node;
	    	newnode->exp = e;
                newnode->coeff = c;
                newnode->next = NULL;  
		return newnode;
     }   
};
poly_list add_poly(poly_list l1,poly_list l2)
   {
	   poly_list lst3;
	   node *h3 = lst3.get_head();
	   node *h1 = l1.get_head();
           node *h2 = l2.get_head();
           while(h1!=NULL && h2!=NULL)
           {
	 	 if(h1->exp > h2->exp)
	         {
		      /*insert node from list1*/
                      lst3.append(h1->exp,h1->coeff);		  
                      h1 = h1->next;
                 }
                 else if(h2->exp > h1->exp)
                   {    /*insert node from list2*/
		       lst3.append(h2->exp,h2->coeff);		     
		      h2 = h2->next;
                 } else
		{/*two exponents are equal. Add the terms*/
                     float sum = h1->coeff +h2->coeff;
                     lst3.append(h1->exp,sum);	
		     h1 = h1->next;
		     h2 = h2->next;
                }
           }
           while(h1!=NULL)
           {/*if list1 has extra nodes, add them*/
                 lst3.append(h1->exp,h1->coeff);		  
                      h1 = h1->next;
	     }
	   while(h2!=NULL)
           {/*if list2 has extra nodes, add them*/
                 lst3.append(h2->exp,h2->coeff);		     
		 h2 = h2->next;
	     }
	      return lst3;
    }
int main()
{
     poly_list lst1,lst2,lst3;
     cout<<"For the first polynomial\n";
    for(int i = 0;i<5;i++)
     {
          int n;float m;
         cout<<"Enter co-efficient and exponent of term (-1 -1 to end):";
          cin>>m;
	  cin>>n;
	  if(n==-1)
              break;	  	
          lst1.append(n,m);
     }
    cout<<"First polynomial  is ";
     lst1.display();
    cout<<"For the seecond polynomial\n";
    for(int i = 0;i<5;i++)
     {
          int n;float m;
          cout<<"Enter co-efficient and exponent of term (-1 -1 to end):";
          cin>>m;
	  cin>>n;
 	 if(n==-1)
              break;	 	  	
          lst2.append(n,m);
     }
     cout<<"The second list is ";
     lst2.display();
     lst3 = add_poly(lst1,lst2);
     cout<<"The resultant polynomial  is";
     lst3.display();
}

15. Write a function to reverse a singly linked list.

You need to recursively set next link to previous node.

When you reach end of list, that is if node->next is NULL, that node should be made as head. In order to maintain this value across recursive calls, head should be made as static variable.

Recursive algorithm for linked list reversal

set current node = l1
if it is lastnode set head = l1
set l2 = nextnode
reverse list from l2 to end of list recursively
set l2->next = l1
set l1->next = NULL
return head
this returned value is discarded except for first call of function

But if you want to write a non-recursive reversal, you should use 3 pointers and a loop
1) set l1, l2,l3 to head, second and third nodes respectively
2) Now link l2 to l1 instead of l1 to l2
3) Now move to next set of 3 nodes (this is where l3 is useful)
4) repeat steps 2 to 3 until end of list

 NODEPTR reverse_list(NODEPTR l1)
 {
    static NODEPTR head;
    if(l1->next==NULL)
   {
       head = l1;
       return l1;
   }
   else
  {		
      NODEPTR l2 = l1->next;
      reverse_list(l2);
      l2->next = l1;
      l1->next = NULL;
      return head;
   }		
}     
/*function call */
head = reverse_list(head);

 NODEPTR reverse_list_nr(NODEPTR head)
 {
      NODEPTR p1,p2,p3;
      p1 = head;
      p2 = p1->next;
      p3 = p2->next;
      p1->next = NULL;
      while(p3!=NULL)
     {
           p2->next = p1;
           p1 = p2;
           p2 = p3;
           p3 = p3->next;
      }
      p2->next = p1;
      return p2;	
} 	   
  
/*function call */
head = reverse_list_nr(head);

16. Write a function to conacatenate two singly linked lists

The program finds the last node of first linked list and then links this to the head of second linked list.

 #include<stdio.h>  
#include<stdlib.h>
 struct node  
 {  
   int n;  
   struct node *next;   
 };  
 typedef struct node * NODEPTR;   
NODEPTR find_lastnode(NODEPTR head);
 void concat(NODEPTR head1,NODEPTR head2)
 {
     NODEPTR lastnode = find_lastnode(head1);
     if(lastnode!=NULL)
         lastnode->next = head2;
 }
 NODEPTR create_node(int value)  
 {  
   NODEPTR temp = (NODEPTR) malloc(sizeof(struct node));  
    temp->next = NULL;  
   temp->n = value;  
   return temp;  
 }  
 NODEPTR append_node(NODEPTR head, NODEPTR newnode)  
 {  
    NODEPTR temp = head;
    if(temp==NULL)
      return newnode;
    while(temp->next !=NULL)
	temp = temp->next;
    temp->next = newnode;
    return head;  
 } 
 

  void display_nodes(NODEPTR head)  
 {  
   NODEPTR temp = head;//redundant 
   while (temp!= NULL)  
   {  
     printf("%d====>",temp->n);  
     temp = temp->next;  
   }  
   printf("\n");
 } 

NODEPTR find_lastnode(NODEPTR nd)
{
   while(nd!=NULL && nd->next!=NULL)
     nd = nd->next;
   return nd;
}
   
  

 int main()  
 {  
     NODEPTR head1,head2;  
     NODEPTR newnode,dnode;  
     int numnodes,i;  
     //initialize head  
     head1 =  head2 = NULL;  
     printf("Number of nodes in first list = ");  
     scanf("%d",&numnodes);  
     printf("Enter nodes of first list:");
     for(i = 0;i<numnodes;i++)  
     {  
       int value;  
       NODEPTR newnode;  
       printf("node value=");  
       scanf("%d",&value);  
       newnode = create_node(value);  
       head1 = append_node(head1,newnode);      
     }  
     printf("The first list now is ");  
     display_nodes(head1);
 
     printf("Number of nodes in second list = ");  
     scanf("%d",&numnodes);  
     printf("Enter nodes of second list:");
     for(i = 0;i<numnodes;i++)  
     {  
       int value;  
       NODEPTR newnode;  
       printf("node value=");  
       scanf("%d",&value);  
       newnode = create_node(value);  
       head2 = append_node(head2,newnode);      
     }  
     printf("The second list now is ");  
     display_nodes(head2); 
     concat(head1,head2);  
     printf("The concatenated list is");
     display_nodes(head1);    
           
 }

17. Write a function to print the nodes of a singly linked list in reverse order. That is, print from last node to first node.

This can be easily done in doubly linked list easily as it has prev link in each node. But SLL does not have prev link.

So the solution has to be written using recursion

if node is node NULL
call function recursively for next node
print the current node

So we recursively call the function for next node each time until we reach NULL. Now the nodes are printed and stack frames are popped out.

e.g.
Let us look at a list like this

10 -18 - 2 - 5

Now the function call works like this

call function for 10
call function for 18
call function for 2
call function for 5
call function for NULL
return from function
print 5 and return from fn
print 2 and return from fn
print 18 and return from fn
print 10 and return from fn

 void display_nodes_reverse(NODEPTR nd)  
 {  
    if( nd!=NULL)
     {
         display_nodes_reverse(nd->next);
         printf("%d--->",nd->n);
     }
 }

18. What is the best algorithm for sorting a linked list. Explain it and write the function.

Insertion sorting is best method for sorting a linked list.

In insertion sorting, each node of a linked list is taken and inserted into the right location.

To start with we can have an empty linked list called slist. We remove one node at a time- first node from unsorted list and then insert this node into the sorted list by finding its correct location.

#include<stdio.h>  
#include<stdlib.h>
 struct node  
 {  
   int n;  
   struct node *next;   
 };  
 typedef struct node * NODEPTR;   
 NODEPTR sort_list(NODEPTR head)
 {
    NODEPTR newhead = NULL;
    while(head!=NULL)
    {
       NODEPTR temp = head;  
       head = head ->next;     
       temp->next = NULL;
       //remove one node at a time   
      newhead = insert_sorted(newhead,temp);
       //insert it into sorted list
     }
     return newhead;
}
 NODEPTR create_node(int value)  
 {  
   NODEPTR temp = (NODEPTR) malloc(sizeof(struct node));  
    temp->next = NULL;  
   temp->n = value;  
   return temp;  
 } 

 NODEPTR append_node(NODEPTR head, NODEPTR newnode)  
 {  
    NODEPTR temp = head;
    if(temp==NULL)
      return newnode;
    while(temp->next !=NULL)
	temp = temp->next;
    temp->next = newnode;
    return head;  
 } 

 void display_nodes(NODEPTR head)  
 {  
   NODEPTR temp = head;//redundant 
   while (temp!= NULL)  
   {  
     printf("%d====>",temp->n);  
     temp = temp->next;  
   }  
   printf("\n");
 } 
 
NODEPTR insert_sorted(NODEPTR head,NODEPTR newnode)
{
      if(head ==NULL)
         return newnode;
      NODEPTR temp=head,prevnode;
      while(temp!=NULL &&temp->n<newnode->n)
      {
	   prevnode=temp;
           temp = temp->next;
      }
      if(temp==head)
          /*insert at head*/
         {
	   newnode->next = head;
           return newnode;
         }
     prevnode->next = newnode;
     newnode->next = temp;
     return head;
}
 int main()  
 {  
     NODEPTR head;  
     NODEPTR newnode,dnode;  
     int numnodes,i;  
     //initialize head  
     head =  NULL;  
     printf("Number of nodes = ");  
     scanf("%d",&numnodes); 
     
     for(i = 0;i<numnodes;i++)  
     {  
       int value;  
       NODEPTR newnode;  
       printf("node value=");  
       scanf("%d",&value);  
       newnode = create_node(value);  
       head = append_node(head,newnode);      
     }  
     printf("The linked list now is ");  
     display_nodes(head); 
   
     head = sort_list(head);
      printf("The linked list now is ");  
     display_nodes(head);               
 }

19. Write a function to insert element to a sorted circular list.

Here you need to find a node with value just greater than new value and insert the node before this.

If the list is empty, newnode becomes head node.

If the new node is smaller than first node, then you need to add the node at the begining.

  #include<stdio.h>  
#include<stdlib.h>
 struct node  
 {  
   int n;  
   struct node *next;   
 };  
 typedef struct node * NODEPTR;  
 NODEPTR insert_node_asc(NODEPTR head, NODEPTR newnode)  
 {  
    NODEPTR temp = head,prevnode=NULL;  
    if(head==NULL) 
    {
       newnode->next = newnode; 
       return newnode;
     }
    if(newnode->n <head->n)
    {/*insert as first node*/
        NODEPTR lastnode = head;
        do 
          lastnode = lastnode->next;
        while (lastnode->next!=head);
        lastnode->next = newnode;
        newnode->next = head;
        head = newnode;
        return head;
    }
    do
    {
       if(temp->n>newnode->n)
          break;
       prevnode = temp;
       temp = temp->next;
    }while(temp!=head ); 
    prevnode->next = newnode;
    newnode->next  = temp;
    return head;  
 } 
 NODEPTR create_node(int value)  
 {  
   NODEPTR temp = (NODEPTR) malloc(sizeof(struct node));  
    temp->next = NULL;  
   temp->n = value;  
   return temp;  
 } 
 
 void display_nodes(NODEPTR head)  
 {  
   NODEPTR temp = head; 
   if(head==NULL)
	return;
   do  
   {  
     printf("%d---->",temp->n);  
     temp = temp->next;  
   } while(temp!=head);
   printf("\n");
 }  

 int main()  
 {  
     NODEPTR head; 
     int numnodes,i;   
     head =  NULL;  
     printf("Number of nodes = ");  
     scanf("%d",&numnodes);  
     for(i = 0;i<numnodes;i++)  
     {  
       int value;  
       NODEPTR newnode;  
       printf("node value=");  
       scanf("%d",&value);  
       newnode = create_node(value);  
       head = insert_node_asc(head,newnode);  
       display_nodes(head);    
     }  
     printf("The linked list now is "); 
     display_nodes(head);  
        
 }

20. Write a function to reverse a doubly linked list.

To reverse a dll, you must swap previous and next links of each node.

But to move to next node, you should say temp = temp->prev.

If you keep saving current node as head before moving to next, when we reach NULL, head will be last node.

 NODEPTR reverse_list(NODEPTR head )
 {
    NODEPTR temp=head; NODEPTR t1;
    while(temp)
    {
       t1 = temp->prev;
       temp->prev = temp->next;
       temp->next = t1;
       head = temp;
       temp = temp->prev;
    }
    return head; 
}

21. Write a function to rotate the elements of a singly linked list to the right by k.

To rotate a list by k, we just need to see the list from kth location. Right? But what happens at last node? Won't the travesing stop because there is a NULL?

Yes, it does. So we have to link last node back to first node.

There is one more problem. We need to rotate to right by k nodes - which means we have to split the list at len-kth location instead.

So we solve the problem like this.
Find the lenght of list
Find (len-k)th node in the list.
Link last node to first node.
Set head as next node of kth node
Set next of kth node to NULL. (split the list)

e.g.
list is
10--20--30--40--50--60--70--80
k is
3

len-k+1 = 5

Find 5th node. - 50. Find its next node 60
Set 80->next = 10
Set head = 50->next
set next pointer of 50 to NULL.

Rotate left is similar. But we find kth node instead of len-k

 #include<stdio.h>  
#include<stdlib.h>
 struct node  
 {  
   int n;  
   struct node *next;   
 };  
 typedef struct node * NODEPTR;   

 NODEPTR create_node(int value)  
 {  
   NODEPTR temp = (NODEPTR) malloc(sizeof(struct node));  
    temp->next = NULL;  
   temp->n = value;  
   return temp;  
 } 
 
 NODEPTR append_node(NODEPTR head, NODEPTR newnode)  
 {  
    NODEPTR temp = head;
    if(temp==NULL)
      return newnode;
    while(temp->next !=NULL)
	temp = temp->next;
    temp->next = newnode;
    return head;  
 } 
int find_size(NODEPTR nd)
{
    int s = 0;
    while(nd!=NULL)
    {
       s++;
       nd = nd->next;
    }
    return s;
}
NODEPTR find_split_point(NODEPTR nd,int k)
{
    int count = find_size(nd); 
    NODEPTR prevnode;
    int i;
    k = count - k;
    NODEPTR temp = nd;
    for(i=1;i<k;i++)
    {
      prevnode = temp;
      temp = temp->next;
    } 
    return temp;
}
 
NODEPTR find_previous(NODEPTR nd, NODEPTR n2)
{
     while(nd!=NULL && nd->next!=n2)
         nd = nd->next;
     if(nd->next==n2)
        return nd;
     else
        return NULL;
}
NODEPTR find_last_node(NODEPTR nd )
{
     while(nd!=NULL && nd->next!=NULL)
         nd = nd->next;
    return nd;
}
NODEPTR rotate_nodes(NODEPTR head,int k)
{    
  NODEPTR prevnode;
  NODEPTR kthnode = find_split_point(head,k);
  if(kthnode!=NULL)
    {
       NODEPTR lastnode = find_last_node(head); 
       if(lastnode==NULL  )
       {
	  printf("error in link. Can not rotate");
          return NULL;
        }
       lastnode->next = head; 
       head = kthnode->next;
       kthnode->next = NULL; 
       return head;
   }
   return NULL;
} 
 void display_nodes(NODEPTR head)  
 {  
   NODEPTR temp = head;//redundant 
   while (temp!= NULL)  
   {  
     printf("%d====>",temp->n);  
     temp = temp->next;  
   }  
   printf("\n");
 }  
 int main()  
 {  
     NODEPTR head;  
     NODEPTR newnode,dnode;  
     int numnodes,i,k;  
     //initialize head  
     head =  NULL;  
     printf("Number of nodes = ");  
     scanf("%d",&numnodes);  
     
     for(i = 0;i<numnodes;i++)  
     {  
       int value;  
       NODEPTR newnode;  
       printf("node value=");  
       scanf("%d",&value);  
       newnode = create_node(value);  
       head = append_node(head,newnode);      
     }  
     printf("The linked list now is ");  
     display_nodes(head); 

      printf("k = ");  
       scanf("%d",&k); 
     NODEPTR temp = rotate_nodes(head,k);
     if(temp!=NULL)
        {
	   head = temp;
	   printf("The rotated list by %d nodes is",k);
           display_nodes(head);
        }
}

22. Given an unsorted linked list, and without using a temporary buffer, write a function that will delete any duplicates from the linked list.

Here 2 loops are used. In the outer loop, a node is taken and in inner loop this is compared with all subsequent nodes and if there is dupicate it is removed by linking its previous node to its next node.

So the complexity of algorithm is O(n2)

We can use two other methods for removing duplicates
a) Sort the list and compare each element with next element. If it is a duplicate, delete it.

b) Use a hash array. When a node is encountered, check if its value is in hash array, delete it. If not, store its value in hash array.

 #include<stdio.h>  
#include<stdlib.h>
 struct node  
 {  
   int n;  
   struct node *next;   
 };  
 typedef struct node * NODEPTR;   
#define MAX 10000

 NODEPTR create_node(int value)  
 {  
   NODEPTR temp = (NODEPTR) malloc(sizeof(struct node));  
    temp->next = NULL;  
   temp->n = value;  
   return temp;  
 } 

 NODEPTR append_node(NODEPTR head, NODEPTR newnode)  
 {  
    NODEPTR temp = head;
    if(temp==NULL)
      return newnode;
    while(temp->next !=NULL)
	temp = temp->next;
    temp->next = newnode;
    return head;  
 } 

 void display_nodes(NODEPTR head)  
 {  
   NODEPTR temp = head;//redundant 
   while (temp!= NULL)  
   {  
     printf("%d====>",temp->n);  
     temp = temp->next;  
   }  
   printf("\n");
 } 
 
void remove_duplicates_hash(NODEPTR head)
{
    NODEPTR temp = head;
    NODEPTR prev = head;
    int hash[MAX]={0};
    hash[temp->n] = temp->n;
    temp = temp->next;
    while(temp!=NULL)
    {
         int num = temp->n;
         if(hash[num]==num)
          {
              delete_node(temp,prev);
              temp = prev->next;
          }
         else
         {
            hash[num]=num;
            prev = temp;         
            temp = temp->next;
         }
    }
}

void delete_node(NODEPTR temp, NODEPTR prev)
{
      prev->next = temp->next;
      free(temp);
}
NODEPTR insert_sorted(NODEPTR head,NODEPTR newnode)
{
      if(head ==NULL)
         return newnode;
      NODEPTR temp=head; NODEPTR prevnode;
      while(temp!=NULL &&temp->n<newnode->n)
      {
	   prevnode=temp;
           temp = temp->next;
      }
      if(temp==head)
          /*insert at head*/
         {
	   newnode->next = head;
           return newnode;
         }
     prevnode->next = newnode;
     newnode->next = temp;
     return head;
}

 NODEPTR sort_list(NODEPTR head)
 {
    NODEPTR newhead = NULL;
    while(head!=NULL)
    {
       NODEPTR temp = head;
       head =  head->next;
       temp->next = NULL;  
       
       newhead = insert_sorted(newhead,temp);      
       //insert it into sorted list
     }
     return newhead;
}

void delete_nextnode(NODEPTR temp)
{
     if(temp->next)
     {
        NODEPTR d1 = temp->next;
        temp->next = temp->next->next;
	free(d1);
     }
}

void remove_duplicates(NODEPTR head)
 {
    NODEPTR temp=head;
    while(temp!=NULL)
    {
        NODEPTR n1 = temp;
        NODEPTR prevnode = n1;
        NODEPTR n2 = temp->next;
        /*remove all duplicates of n1*/
        while(n2!=NULL)
        {
           if(n1->n == n2->n)
            {
                prevnode->next = n2->next;
                free(n2);
                n2 = prevnode->next;
            }else{
            prevnode = n2 ;
            n2 = n2->next;
           }
        }
        temp = temp->next;
     }
} 

NODEPTR remove_duplicates_sorted(NODEPTR head)
{
    head = sort_list(head);
    NODEPTR temp=head;
    NODEPTR prev_node  = temp;
    temp = temp->next;
    while(temp!=NULL)
    {
        if(temp->n == prev_node->n)
        /* we have duplicate. Delete it*/
        {
             delete_nextnode(prev_node);             
             temp = prev_node->next;
        }else
        {
            prev_node = temp;
            temp = temp->next;
         }
    }
    return head;
}

 int main()  
 {  
     NODEPTR head;  
     NODEPTR newnode,dnode;  
     int numnodes,i;  
     //initialize head  
     head =  NULL;  
     printf("Number of nodes = ");  
     scanf("%d",&numnodes);  
     
     for(i = 0;i<numnodes;i++)  
     {  
       int value;  
       NODEPTR newnode;  
       printf("node value=");  
       scanf("%d",&value);  
       newnode = create_node(value);  
       head = append_node(head,newnode);      
     }  
     printf("The linked list now is ");  
     display_nodes(head) ;
     head = remove_duplicates_sorted(head);
     printf("The linked list now is ");  
     display_nodes(head);               
 }

23. Write a function to delete a node of a singly linked list, given only that node

Normally when we delete a node, we link previous node of delnode to next node of del node, so that link is not broken. But here, as we have no other information- no head node, we can not find the previous node.

So we copy the data of next node to current node and then delete next node instead.
nd->n = nd->next->n
nd->next = nd->next->next
free(nd->next)

Please note that this method fails if the node to be deleted is the last node.

 #include<stdio.h>  
#include<stdlib.h>
 struct node  
 {  
   int value;  
   struct node *next;   
 };  
 typedef struct node * NODEPTR;  

 NODEPTR delete_node_given_onend( NODEPTR dnode)
 {
      NODEPTR nextnode = dnode->next;
      if(nextnode!=NULL)
      {
         dnode->value = nextnode->value;        
         dnode->next = nextnode->next;        
         free(nextnode);
      }
      else
       printf("Not possible as this is last node");
 }
 NODEPTR create_node(int value)  
 {  
   NODEPTR temp = (NODEPTR) malloc(sizeof(struct node));  
    temp->next = NULL;  
   temp->value = value;  
   return temp;  
 } 

 NODEPTR append_node(NODEPTR head, NODEPTR newnode)  
 {  
    NODEPTR temp = head;
    if(temp==NULL)
      return newnode;
    while(temp->next !=NULL)
	temp = temp->next;
    temp->next = newnode;
    return head;  
 } 

 void display_nodes(NODEPTR head)  
 {  
   NODEPTR temp = head;//redundant 
   while (temp!= NULL)  
   {  
     printf("%d====>",temp->value);  
     temp = temp->next;  
   }  
   printf("\n");
 } 

 NODEPTR find_node(NODEPTR temp, int val)
 {
      while(temp)
      {
         if(temp->value==val)
            return temp;
        temp = temp->next;
     }
     return NULL;//node not found
}

 int main()  
 {  
     NODEPTR head;  
     NODEPTR newnode,dnode;  
     int numnodes,i;  
     //initialize head  
     head =  NULL;  
     printf("Number of nodes = ");  
     scanf("%d",&numnodes);  
     
     for(i = 0;i<numnodes;i++)  
     {  
       int value;  
       NODEPTR newnode;  
       printf("node value=");  
       scanf("%d",&value);  
       newnode = create_node(value);  
       head = append_node(head,newnode);      
     }  
     printf("The linked list now is ");  
     display_nodes(head); 
    
     printf("Enter node to be deleted:");
     scanf("%d",&i);
     NODEPTR nd = find_node(head,i);
     if(nd!=NULL)
       delete_node_given_onend(nd); 
     printf("Now the list is ");
     display_nodes(head);     
 }

24. Write a function to merge two sorted linked lists

The program works as follows
1) detach one node from head of list1
2) detach a node from head of list2
3) whichever is smaller link it to the merged list and move to next node
4) repeat steps 1 to 3 until either of the lists is empty
5) move all the nodes of the non-empty list to merged list

 #include<stdio.h>  
#include<stdlib.h>
 struct node  
 {  
   int val;  
   struct node *next;   
 };   
 typedef struct node *NODEPTR;
NODEPTR append_node(NODEPTR head,NODEPTR nd);
NODEPTR merge_sorted(NODEPTR head1,NODEPTR head2)
{
  NODEPTR newlist = NULL;
  while(head1!=NULL && head2!=NULL )
 {
    if(head1->val <head2->val)
    {/*add a node from list1*/
    NODEPTR temp = head1;
    head1 = head1->next; 
    temp->next = NULL;
    newlist = append_node(newlist,temp);
    }
    else
    {/*add a node from list2*/
    NODEPTR temp = head2;
    head2 = head2->next; 
    temp->next = NULL;
    newlist = append_node(newlist,temp);
    }
 }
 while(head1!=NULL)
 {/*add all remaining nodes*/
  NODEPTR temp = head1;
  head1 = head1->next; 
  temp->next = NULL;
  newlist = append_node(newlist,temp);
  }
 while(head2!=NULL)
 {
  NODEPTR temp = head2;
  head2 = head2->next; 
  temp->next = NULL;
  newlist = append_node(newlist,temp);
 }
 return newlist;  
}   

 NODEPTR create_node(int value)  
 {  
   NODEPTR temp = (NODEPTR) malloc(sizeof(struct node));  
    temp->next = NULL;  
   temp->val = value;  
   return temp;  
 } 
 
 NODEPTR append_node(NODEPTR head, NODEPTR newnode)  
 {  
    NODEPTR temp = head;
    if(temp==NULL)
      return newnode;
    while(temp->next !=NULL)
       temp = temp->next;
    temp->next = newnode;
    return head;  
 }  

 void display_nodes(NODEPTR head)  
 {  
   NODEPTR temp = head;//redundant 
   while (temp!= NULL)  
   {  
     printf("%d====>",temp->val);  
     temp = temp->next;  
   }  
   printf("\n");
 }   

 int main()  
 {  
     NODEPTR head1,head2,head3;  
     NODEPTR newnode,dnode;  
     int numnodes1,numnodes2,i;  
     //initialize head  
     head1 = head2 =  NULL;  
     printf("Number of nodes in first SORTED list = ");  
     scanf("%d",&numnodes1);       
     for(i = 0;i<numnodes1;i++)  
     {  
       int value;  
       NODEPTR newnode;  
       printf("node value=");  
       scanf("%d",&value);  
       newnode = create_node(value);  
       head1 = append_node(head1,newnode);      
     }  
     printf("The linked list 1  now is ");  
     display_nodes(head1); 
     printf("Number of nodes in second SORTED list  = ");  
     scanf("%d",&numnodes2);       
     for(i = 0;i<numnodes2;i++)  
     {  
       int value;  
       NODEPTR newnode;  
       printf("node value=");  
       scanf("%d",&value);  
       newnode = create_node(value);  
       head2 = append_node(head2,newnode);      
     } 
      printf("List 2 is  ");
     display_nodes(head2);   
     head3 = merge_sorted(head1,head2);
     printf("Now the merged list is ");
     display_nodes(head3);              
 }

25. Write a function to find the number of nodes in singly linked list. Write another function to find this length using recursion

To find the length without using recursion is simple - just increment the count while travesing the list and return this count

To find length using recursion, wereturn previous length +1 . And when node is NULL, we return 0. So that last node returns 1, last -1th node returns 2 and so on.

 #include<stdio.h>  
#include<stdlib.h>
 struct node  
 {  
   int n;  
   struct node *next;   
 };  
 typedef struct node * NODEPTR;  
  
 int get_count(NODEPTR temp)
 {
      int c = 0;
      while(temp)
      {
           c++;
           temp = temp->next;
      }
     return c; 
}
int get_count_recursive(NODEPTR temp)
{
    if(temp!=NULL)
   {
       return get_count_recursive( temp->next)+1;
   }
   else return 0;
}
 NODEPTR create_node(int value)  
 {  
   NODEPTR temp = (NODEPTR) malloc(sizeof(struct node));  
    temp->next = NULL;  
   temp->n = value;  
   return temp;  
 } 
  
 NODEPTR append_node(NODEPTR head, NODEPTR newnode)  
 {  
    NODEPTR temp = head;
    if(temp==NULL)
      return newnode;
    while(temp->next !=NULL)
	temp = temp->next;
    temp->next = newnode;
    return head;  
 } 
 
 void display_nodes(NODEPTR head)  
 {  
   NODEPTR temp = head;//redundant 
   while (temp!= NULL)  
   {  
     printf("%d====>",temp->n);  
     temp = temp->next;  
   }  
   printf("\n");
 } 
 
 int main()  
 {  
     NODEPTR head;  
     //initialize head  
     head =  NULL;        
     while(1){
       int value;  
       NODEPTR newnode;  
       printf("node value (-1 to stop)=");  
       scanf("%d",&value); 
       if(value==-1) 
            break; 
       newnode = create_node(value);  
       head = append_node(head,newnode);      
     }
     printf("The linked list now is ");  
     display_nodes(head);
     printf("The number of nodes in sll is %d\n",get_count(head));
     printf("The number of nodes in sll using recursion is %d\n",get_count(head));           
 }

26. Write a function to merge sort a given linked list

The list can be merge sorted using divide and conquer technique.

1) The list is split into two parts l1 and l2 at mid point.
To find the midpoint of list, the famous two pointers slow which moves one node at a time and fast which moves two nodes at a time are used.

2) These are recursively merge sorted as long as list has more than one node

3) Now the two sorted lists l1 and l2 are merged recursively

 #include<stdio.h>  
#include<stdlib.h>
 struct node  
 {  
   int val;  
   struct node *next;   
 };  
 typedef struct node * NODEPTR; 
 NODEPTR merge_sorted_lists(NODEPTR h1,NODEPTR h2);

 NODEPTR create_node(int value)  
 {  
   NODEPTR temp = (NODEPTR) malloc(sizeof(struct node));  
    temp->next = NULL;  
   temp->val = value;  
   return temp;  
 } 
 
 NODEPTR append_node(NODEPTR head, NODEPTR newnode)  
 {  
    NODEPTR temp = head;
    if(temp==NULL)
      return newnode;
    while(temp->next !=NULL)
	temp = temp->next;
    temp->next = newnode;
    return head;  
 } 
 void display_nodes(NODEPTR head)  
 {  
   NODEPTR temp = head; 
   while (temp!= NULL)  
   {  
     printf("%d--->",temp->val);  
     temp = temp->next;  
   }  
   printf("\n");
 } 

NODEPTR split_list(NODEPTR head)
{
    NODEPTR slow,fast;
    slow =head; 
    fast = head;
    if(head==NULL || head->next==NULL)     
       return head;
    NODEPTR temp;
    while(fast!=NULL)         
    {       
        fast = fast->next;        
        if(fast!=NULL){
           temp = slow;
           fast = fast->next;
           slow = slow->next;
        }           
     }     
     temp->next  = NULL;
     return slow;
}
      

NODEPTR merge_sort(NODEPTR head)
{
     if(head==NULL || head->next==NULL)
       return head;
     NODEPTR mid = split_list(head);
     head = merge_sort(head);
     mid = merge_sort(mid);
     head = merge_sorted_lists(head,mid);
     return head;
}

 
NODEPTR merge_sorted_lists(NODEPTR head1,NODEPTR head2)
{
	NODEPTR newlist = NULL;
	while(head1!=NULL && head2!=NULL )
	{
	   if(head1->val <head2->val)
		{
		NODEPTR temp = head1;
		head1 = head1->next; 
		temp->next = NULL;
		newlist = append_node(newlist,temp);
		}
	   else
		{
		NODEPTR temp = head2;
		head2 = head2->next; 
		temp->next = NULL;
		newlist = append_node(newlist,temp);
		}
	}
	while(head1!=NULL)
	{
		NODEPTR temp = head1;
		head1 = head1->next; 
		temp->next = NULL;
		newlist = append_node(newlist,temp);
		}
	while(head2!=NULL)
	{
		NODEPTR temp = head2;
		head2 = head2->next; 
		temp->next = NULL;
		newlist = append_node(newlist,temp);
	}
	return newlist;  
}       


 int main()  
 {  
     NODEPTR head1,head2;  
     NODEPTR newnode,dnode;  
     int numnodes1,numnodes2,i;  
     //initialize head  
     head1 = head2 =  NULL;  
     printf("Number of nodes in list  = ");  
     scanf("%d",&numnodes1);       
     for(i = 0;i<numnodes1;i++)  
     {  
       int value;  
       NODEPTR newnode;  
       printf("node value=");  
       scanf("%d",&value);  
       newnode = create_node(value);  
       head1 = append_node(head1,newnode);      
     }  
     printf("The linked list    now is ");  
     display_nodes(head1); 
     head1 = merge_sort(head1); 
     printf("Now the merged list is ");
     display_nodes(head1);   
           
 }

27. Write a function to add a node newnd before a given node k in a doubly linked list. k is not NULL

Inserting a node in the middle of doubly linked list needs modification of 4 links.
k->prev->next = newnode
newnode->prev = k->prev
k->prev = newnode
newnode->next = k

And we have to check if k->prev is not null because, if there is no previous node for k, it means k is head of list. In that case k->prev->next will crash the program.

 NODEPTR insert_before_k(NODEPTR head, NODEPTR k, NODEPTR newnode)  
 {  
      NODEPTR prevnode = k->prev;
   
      if(prevnode!=NULL)
         prevnode->next = newnode;

      newnode->prev = prevnode;
      newnode->next = k;
      k->prev = newnode;

      if(prevnode==NULL)/*k is head*/
        head = newnode;
      return head; 
 }

28. Given two linked lists, write a function to return the union of these two lists.

To find union, we need to copy the elements which are common to both the lists into the resultant list. We should avoid duplicates.

So we should copy all the elements of first list. Next copy only those elements of second list which are not present in first list.

 #include<stdio.h>  
#include<stdlib.h>
 struct node  
 {  
   int n;  
   struct node *next;   
 };  
 typedef struct node * NODEPTR;   
NODEPTR create_node(int n);
NODEPTR append_node(NODEPTR,NODEPTR);

NODEPTR find_union(NODEPTR head1, NODEPTR head2)
 {
    NODEPTR head3 = NULL;
    NODEPTR temp = head1;
    /*copy all nodes of first list*/
    while(temp!=NULL){
        head3 = append_node(head3, create_node(temp->n));
        temp = temp->next;
    }
    temp = head2;
    while(temp!=NULL)
    { 
        NODEPTR temp1 = head3;
        while(temp1!=NULL && temp1->n!=temp->n)
            temp1=temp1->next;
        if(!temp1){
            NODEPTR newnode = create_node( temp->n);
             head3=append_node( head3,newnode);
        }
        temp = temp->next;
    }
    return head3;
}
 NODEPTR create_node(int value)  
 {  
   NODEPTR temp = (NODEPTR) malloc(sizeof(struct node));  
   temp->next = NULL;  
   temp->n = value;  
   return temp;  
 } 
 NODEPTR append_node(NODEPTR head, NODEPTR newnode)  
 {  
    NODEPTR temp = head;
    if(temp==NULL)
      return newnode;
    while(temp->next !=NULL)
	temp = temp->next;
    temp->next = newnode;
    return head;  
 } 
 void display_nodes(NODEPTR head)  
 {  
   NODEPTR temp = head;//redundant 
   while (temp!= NULL)  
   {  
     printf("%d====>",temp->n);  
     temp = temp->next;  
   }  
   printf("\n");
 }  

 int main()  
 {  
     NODEPTR head1, head2;  
     NODEPTR newnode,dnode;  
     int numnodes,i;  
     head1 = NULL;
     head2 =  NULL;  
     printf("Number of nodes = ");  
     scanf("%d",&numnodes);  
     
     for(i = 0;i<numnodes;i++)  
     {  
       int value;  
       NODEPTR newnode;  
       printf("node value=");  
       scanf("%d",&value);  
       newnode = create_node(value);  
       head1 = append_node(head1,newnode);      
     }  
     printf("The linked list now is ");  
     display_nodes(head1);
     printf("Number of nodes of second list is = ");  
     scanf("%d",&numnodes);  
     
     for(i = 0;i<numnodes;i++)  
     {  
       int value;  
       NODEPTR newnode;  
       printf("node value=");  
       scanf("%d",&value);  
       newnode = create_node(value);  
       head2 = append_node(head2,newnode);      
     }  
     printf("The linked list now is ");  
     display_nodes(head2);
     NODEPTR head3 = find_union(head1,head2);
     printf("The union of two lists is ");
     display_nodes(head3);    
 }

29. Write a function to remove every kth node from a circular list, until only one node is left.

You should write a loop to skip k-1 nodes and then delete kth node. You should also write an outer loop to continue this process until only one node is left.

Outer loop must stop when only one node is left. That is when head->next is head.

This problem is called Josephus problem.

 #include<stdio.h>  
#include<stdlib.h>
 struct node  
 {  
   int n;  
   struct node *next;   
 };  
 typedef struct node * NODEPTR;  
 NODEPTR delete_nodes(NODEPTR head,int k)
{
    NODEPTR temp = head;
    NODEPTR prevnode = NULL;
    while(temp->next !=temp) 
    {
           int i; 
           for(i=1;i<k;i++)
           {
             prevnode = temp;
             temp = temp->next;
           }
           if(prevnode!=NULL)
            {
               printf("Deleting the node %d\n",temp->n);
               prevnode->next = prevnode->next->next;
               free(temp);
            }
            temp = prevnode->next;
      }
      return temp;
} 
 NODEPTR create_node(int value)  
 {  
   NODEPTR temp = (NODEPTR) malloc(sizeof(struct node));  
    temp->next = NULL;  
   temp->n = value;  
   return temp;  
 }  
 NODEPTR append_node(NODEPTR head, NODEPTR newnode)  
 {  
    NODEPTR temp = head;
    if(head==NULL)
      {
        newnode->next = newnode;
        return newnode;
      }
    while(temp->next !=head)
	temp = temp->next;
    temp->next = newnode;
    newnode->next = head;
    return head;  
 } 
 
 void display_nodes(NODEPTR head)  
 {  
   NODEPTR temp = head; 
   if(head==NULL)
	return;
   do  
   {  
     printf("%d---->",temp->n);  
     temp = temp->next;  
   } while(temp!=head);
   printf("\n");
 }   
 int main()  
 {  
     NODEPTR head; 
     int numnodes,i;  
     //initialize head  
     head =  NULL;  
     printf("Number of nodes = ");  
     scanf("%d",&numnodes);  
     for(i = 0;i<numnodes;i++)  
     {  
       int value;  
       NODEPTR newnode;  
       printf("node value=");  
       scanf("%d",&value);  
       newnode = create_node(value);  
       head = append_node(head,newnode);      
     }  
     printf("The linked list now is ");  
     display_nodes(head);   
     printf("k=");
     scanf("%d",&i);
     head = delete_nodes(head,i);
     printf("The node remaining is %d\n",head->n);
 }

30. Given two polynomials as linked lists, return a linked list which represents the product of two polynomials.

When we multiply two polynomials, each term in first polynomial is multiplied with every term in second polynomial. In the product for each term, the exponants are added together and co-effecients are multiplied.

e.g.
(x^2+1) * (x^2+2x+5)
= x^4+x^2+2x^3+2x+5x^2+5

But in the resultant polynomial there may be multiple terms with same exponent in the product and we need to simplify them.

e.g. x^4+x^2+2x^3+2x+5x^2+5 =
x^4+2x^3+6x^2+2x+5

So we search in the resultant list for a term with given exponent. If found we add the co-effecient to this term. If not found, we create a new node with this exponent.

 #include<stdio.h>  
#include<stdlib.h>
 struct node  
 {  
   int coeff;
   int exponent;
   struct node *next;   
 };  
 typedef struct node * NODEPTR;   
 NODEPTR multiply_polynomials(NODEPTR head1, NODEPTR head2)
 {
    NODEPTR head3 = NULL;/*result list*/
    while(head1!=NULL)
    {
        NODEPTR temp = head2;
        while(temp!=NULL)
        {
	 int coeff=temp->coeff*head1->coeff;
                 int exponent = temp->exponent+head1->exponent;
            	NODEPTR nd2 = NULL;
                if(head3!=NULL)  nd2 =  term_with_exp(head3,exponent);
                /*find the term with exponent in the resultant list*/
                if(nd2==NULL){
                  NODEPTR nd = create_node(coeff,exponent);
                  head3 = append_node(head3,nd); 
                }
               else
               {
                  nd2->coeff +=coeff;
               }            
            temp = temp->next;
        }
        head1 = head1->next;
     }
     return head3;  
}
 NODEPTR create_node(int c1,int e1)  
 {  
   NODEPTR temp = (NODEPTR) malloc(sizeof(struct node));  
    temp->next = NULL;  
   temp->coeff = c1; 
   temp->exponent = e1; 
   return temp;  
 } 

 NODEPTR append_node(NODEPTR head, NODEPTR newnode)  
 {  
    NODEPTR temp = head;
    if(temp==NULL)
      return newnode;
    while(temp->next !=NULL)
	temp = temp->next;
    temp->next = newnode;
    newnode->next = NULL;
    return head;  
 } 
 
 void display_nodes(NODEPTR head)  
 {  
   NODEPTR temp = head; 
   while (temp!= NULL)  
   {  
     printf("+");
     if(temp->exponent>0)
         printf("%dX^%d  ",temp->coeff,temp->exponent);  
     else 
         printf("%d",temp->coeff);
     temp = temp->next;  
   }  
   printf("\n");
 } 
 
 NODEPTR term_with_exp(NODEPTR head,int exponent)
 {
      while(head!=NULL)
      {
        if(head->exponent==exponent) 
            return head;
        head = head->next;
      }
      return NULL;
}

 
 int main()  
 {  
     NODEPTR head,head2; 
     NODEPTR prodlist = NULL; 
     NODEPTR newnode,dnode;  
     int numnodes,i;   
     head =  head2 = NULL;  
     printf("Number of terms in first polynomial = ");  
     scanf("%d",&numnodes);  
     
     for(i = 0;i<numnodes;i++)  
     {  
       int c1,e1;  
       NODEPTR newnode;  
       printf("node coeff and node exponent=");  
       scanf("%d %d",&c1,&e1);  
       newnode = create_node(c1,e1);  
       head = append_node(head,newnode);      
     }  
     printf("The first polynomial is ");
     display_nodes(head);
     printf("Number of terms in second polynomial = ");  
     scanf("%d",&numnodes);  
     
     for(i = 0;i<numnodes;i++)  
     {  
       int c1,e1;  
       NODEPTR newnode;  
       printf("node coeff and node exponent=");  
       scanf("%d %d",&c1,&e1);  
       newnode = create_node(c1,e1);  
       head2 = append_node(head2,newnode);      
     }  
     printf("The second polynomial is ");
     display_nodes(head2);
     printf("The product  is ");  
   
     prodlist = multiply_polynomials(head,head2);
     display_nodes(prodlist);           
 }

31. Write a function to append a node to a singly linked list

We need to traverse till last node of the list. Then last node must be linked to new node.

Also note that the function needs to return pointer to first node (head) because if the list is empty, then the newnode will become head of the list.

The caller should use a statement like
head = append(head,10);

struct node *append(struct node *head,int num)
{
     /*create a node*/
     struct node *newnode = malloc(sizeof(struct node));
     newnode->val = num;
     newnode->next = NULL;

     struct node *temp = head;
    /*find last node*/
     while(temp!=NULL && temp->next!=NULL)
        temp = temp->next;
     if(head==NULL)/*empty list*/
         return newnode;
     /*link last node to newnode*/
     temp->next = newnode;
     return head;
}

/***call it like this****/
int main()
{
    ----
    head = append_node(head,24);
   ----
}

32. Write a function to delete a node with a value v from a singly linked list.

We have to traverse the list searching for the value. Once value is found, we should link its previous node to next node so that the node is now detached.

Next we have to release memory.

If the node to be deleted is head, then we have to modify head and set it as second node.

The complexity of operation is O(n)

 #include<stdio.h>  
#include<stdlib.h>
 struct node  
 {  
   int n;  
   struct node *next;   
 };  
 typedef struct node * NODEPTR;   
 
 NODEPTR delete_node(NODEPTR head, int val)
 {
     NODEPTR temp  = head;
     NODEPTR prev = NULL;
     if(head->n==val)
    {/*deleting first node*/   
         head = head->next;
         free(temp);  
     }
    else{
        while (temp !=NULL && temp->n!=val)
        {/*travese till you find value*/
            prev = temp;
            temp = temp->next;
         } 
         if(temp!=NULL )
        { 
           prev->next = temp->next;
           free(temp);
         }
        else
          printf("Value not found\n"); 
    }
    return head;
 } 

 NODEPTR create_node(int value)  
 {  
   NODEPTR temp = (NODEPTR) malloc(sizeof(struct node));  
    temp->next = NULL;  
   temp->n = value;  
   return temp;  
 } 
 
 NODEPTR append_node(NODEPTR head, NODEPTR newnode)  
 {  
    NODEPTR temp = head;
    if(temp==NULL)
      return newnode;
    while(temp->next !=NULL)
	temp = temp->next;
    temp->next = newnode;
    return head;  
 } 
  
 void display_nodes(NODEPTR temp)  
 {   
   while (temp!= NULL)  
   {  
     printf("%d====>",temp->n);  
     temp = temp->next;  
   }  
   printf("\n");
 }  
 int main()  
 {  
     NODEPTR head;  
     NODEPTR newnode,dnode;  
     int numnodes,i;  
     //initialize head  
     head =  NULL;  
     printf("Number of nodes = ");  
     scanf("%d",&numnodes);  
     
     for(i = 0;i<numnodes;i++)  
     {  
       int value;  
       NODEPTR newnode;  
       printf("node value=");  
       scanf("%d",&value);  
       newnode = create_node(value);  
       head = append_node(head,newnode);      
     }  
     printf("The linked list now is ");  
     display_nodes(head); 
     printf("Enter the node to be deleted:");
     scanf("%d",&i);
     head = delete_node(head,i);
     printf("Now the list is ");
     display_nodes(head);   
 }

33. Write a function to delete all the occurances of a given value in a linked list.

Here in a loop we delete nodes of given value and break the loop when value is not found.

We are using a helper function find_node() which searches for the value and returns the node if found, returns NULL if not found. The function also gives as previous node as a pointer parameter. This will be useful in deleting the node.

#include<stdio.h>  
#include<stdlib.h>
 struct node  
 {  
   int n;  
   struct node *next;   
 };  
 typedef struct node * NODEPTR;   
NODEPTR find_node(NODEPTR head,int val,NODEPTR *prevnode);
NODEPTR del_all_nodes(NODEPTR head,int val)
{   
    NODEPTR temp = head; 
    while(head!=NULL)
    {
       NODEPTR prevnode,dnode;
       dnode = find_node(temp,val,&prevnode);
       if(dnode!=NULL)
       {
         temp = dnode->next;/*store this*/
         if(prevnode==NULL)/*head to be deleted*/
         { head =head->next;
           free(dnode);
         }
         else
         {
           prevnode->next = dnode->next;
           free(dnode);
         }          
       }
       else break;
     }
     return head;
} 
 NODEPTR create_node(int value)  
 {  
   NODEPTR temp = (NODEPTR) malloc(sizeof(struct node));  
   temp->next = NULL;  
   temp->n = value;  
   return temp;  
 } 
 
 NODEPTR append_node(NODEPTR head, NODEPTR newnode)  
 {  
    NODEPTR temp = head;
    if(temp==NULL)
         return newnode;
    while(temp->next !=NULL)
	temp = temp->next;
    temp->next = newnode;
    return head;  
 } 
  
 void display_nodes(NODEPTR head)  
 {  
   NODEPTR temp = head;//redundant 
   while (temp!= NULL)  
   {  
     printf("%d====>",temp->n);  
     temp = temp->next;  
   }  
   printf("\n");
 } 
NODEPTR find_node(NODEPTR head,int val,NODEPTR *prevnode)
{
    *prevnode = NULL;
    while(head!=NULL)
    {
        if(head->n==val)
            return head;
        *prevnode = head;
        head = head->next;
    }
    return NULL;
}
 

 int main()  
 {  
     NODEPTR head;  
     NODEPTR newnode,dnode;  
     int numnodes,i;  
     //initialize head  
     head =  NULL;  
     printf("Number of nodes = ");  
     scanf("%d",&numnodes);  
     
     for(i = 0;i<numnodes;i++)  
     {  
       int value;  
       NODEPTR newnode;  
       printf("node value=");  
       scanf("%d",&value);  
       newnode = create_node(value);  
       head = append_node(head,newnode);      
     }  
     printf("The linked list now is ");  
     display_nodes(head); 
     printf("Enter the value to be deleted:");
     scanf("%d",&i);
     head = del_all_nodes(head,i);
     printf("Now the list is ");
     display_nodes(head);               
 }

34. Write a function to split a singly linked list into two halves.

The function finds the midpoint using the two pointer method.

Two pointers are used for traversing. First pointer moves one node at a time. Second pointer moves two nodes at a time. When second pointer has reached end of list, first pointer is at midpoint.

After finding midpoint, the program splits the first half by detaching the node before midpoint and returning midpoint node as second list.

The same algorithm is used for finding the middle of linked list.

And is used to know if there is a loopback in the linked list. If there is a loopback, then slow pointer becomes equal to fast pointer.

#include<stdio.h>  
#include<stdlib.h>
 struct node  
 {  
   int n;  
   struct node *next;   
 };  
 typedef struct node * NODEPTR;  
 NODEPTR create_node(int value);   
 NODEPTR append_node(NODEPTR head, NODEPTR newnode);  
 void display_nodes(NODEPTR head);  
NODEPTR split_list(NODEPTR head)
{
    NODEPTR slow,fast;
    slow =head; 
    fast = head;
    if(head==NULL || head->next==NULL)     
       return head;
    NODEPTR temp;
    while(fast!=NULL)         
    {       
        fast = fast->next;        
        if(fast!=NULL){
           temp = slow;
           fast = fast->next;
           slow = slow->next;
        }           
     }     
     temp->next  = NULL;
     return slow;
}
 NODEPTR create_node(int value)  
 {  
   NODEPTR temp = (NODEPTR) malloc(sizeof(struct node));  
    temp->next = NULL;  
   temp->n = value;  
   return temp;  
 }  

 NODEPTR append_node(NODEPTR head, NODEPTR newnode)  
 {  
    NODEPTR temp = head;
    if(temp==NULL)
      return newnode;
    while(temp->next !=NULL)
	temp = temp->next;
    temp->next = newnode;
    return head;  
 } 
  

 void display_nodes(NODEPTR head)  
 {  
   NODEPTR temp = head;//redundant 
   while (temp!= NULL)  
   {  
     printf("%d====>",temp->n);  
     temp = temp->next;  
   }  
   printf("\n");
 }    


 int main()  
 {  
     NODEPTR head,head2;   
     int numnodes,i;  
     //initialize head  
     head =  NULL;  
     printf("Number of nodes = ");  
     scanf("%d",&numnodes);  
     
     for(i = 0;i<numnodes;i++)  
     {  
       int value;  
       NODEPTR newnode;  
       printf("node value=");  
       scanf("%d",&value);  
       newnode = create_node(value);  
       head = append_node(head,newnode);      
     }  
     printf("The linked list now is ");  
     display_nodes(head);   
     head2 = split_list(head);
     printf("The listsare ");
     display_nodes(head);
     printf("\n");
     display_nodes(head2);
 }

35. Given a linked list , swap alternate nodes of linked list . For eq: 1 2 3 4 will become 2 1 4 3 and 1 2 3 4 5 6 will become 2 1 4 3 6 5

We have to swap the links of two adjacent nodes.

 #include<stdio.h>  
#include<stdlib.h>
 struct node  
 {  
   int n;  
   struct node *next;   
 };  
 typedef struct node * NODEPTR;  
  NODEPTR swap_nodes(NODEPTR head)
{
    NODEPTR prevnode = NULL; 
    NODEPTR temp = head->next;
    head->next = temp->next;
    temp->next = head;
    head = temp;
    temp = head->next->next;
    prevnode = head->next;
    
    while(temp!=NULL)
    {
	 NODEPTR p1,p2;
         p1 = temp;
         p2 = p1->next;
         if(p2!=NULL){
            if(prevnode!=NULL)
               prevnode->next = p2;
            else
               head = p2;
            p1->next = p2->next;
            p2->next = p1;         
         }
         prevnode= temp;
         temp = temp->next; 
     }
     return head;
}
 
 NODEPTR create_node(int value)  
 {  
   NODEPTR temp = (NODEPTR) malloc(sizeof(struct node));  
    temp->next = NULL;  
   temp->n = value;  
   return temp;  
 } 

  
 NODEPTR append_node(NODEPTR head, NODEPTR newnode)  
 {  
    NODEPTR temp = head;
    if(temp==NULL)
      return newnode;
    while(temp->next !=NULL)
	temp = temp->next;
    temp->next = newnode;
    return head;  
 } 

 
 void display_nodes(NODEPTR head)  
 {  
   NODEPTR temp = head;//redundant 
   while (temp!= NULL)  
   {  
     printf("%d====>",temp->n);  
     temp = temp->next;  
   }  
   printf("\n");
 } 


 
 int main()  
 {  
     NODEPTR head;  
     NODEPTR newnode,dnode;   
     //initialize head  
     head =  NULL;   
     while(1){
       int value;  
       NODEPTR newnode;  
       printf("node value (-1 to stop)=");  
       scanf("%d",&value); 
       if(value==-1) 
	  break; 
       newnode = create_node(value);  
       head = append_node(head,newnode);      
     }
     printf("The linked list  is ");  
     display_nodes(head);
     head = swap_nodes(head);
     printf("The linked list after swapping is ");  
     display_nodes(head);           
 }

36. Write a function to find the node where two lists merge.

Merge point is the node where the two lists combine. From merge point, the nodes(addresses - not values) will be common for both nodes.
8--9--12--13--
\--18--19--89
6--9--29-/

Here 18 is the merge point of the two lists.
In this solution,
a) Find the lengths of lists
b) Skip the elements from the longer list till both have equal number of nodes.
c) Traverse lists parallely until they have a common node (with same address, not only value)

Say, first list has 10 elements and second list has 4 elements. From the first list, 6 nodes are traversed. Next list1 and list2 are traversed parallely one node at a time. Adresses of these nodes are compared. When they are equal, we have found our merge point.

For the sake of testing, we can create merged lists by pointing last node of list2 point to 3rd(or any other number) node of list1. The code for this creation is not shown here.

int find_length(NODEPTR head)
{
   int c =0;
   while(head)
   {
      c++;
      head = head->next;
   }
   return c;
}

NODEPTR skip_nodes(NODEPTR head, int num)
{
    while(num)
    {
       head = head->next;
       num--;
    }
    return head;
}

NODEPTR find_merge_point(NODEPTR l1,NODEPTR l2)
{
    int len1 = find_length(l1);
    int len2 = find_length(l2);
    if(len1>len2)
    {
       l1 = skip_nodes(l1,len1-len2);
    }else{
       l2 = skip_nodes(l2,len2-len1);
    }
    while(l1 && l2)
    {
        if(l1==l2)
            return l1;
         l1=l1->next;
         l2 = l2->next;
    }
    return NULL;
}

37. Write a function to delete all the nodes of linked list and release memory used by them

If you say the answer
head = NULL
you are wrong.
You have set list to NULL, but what happens to all the nodes you have allocated memory? They do remain in the program and will cause memory leakage. So we have to free the memory allocated to every node.

So this is what we should do. First node is deleted and freed. The pointer is moved to next node (before deleting first node :)) and that is deleted and so on.

The process is repeated in a loop until we reach end of the list.

 NODEPTR delete_list ( NODEPTR head)
 {
     while(head)
     {
          NODEPTR temp  = head;
          head = head->next;
          free(temp);
      }
     return head;
 }

38. Write a program to delete the nth item from end of a singly linked list

Here we need to find kth node from end recursively and delete it.

To avoid traversing again for finding previous node of kth node, we can use previous node as a pointer parameter to function.

The algorithm to find kth node from end of list (and its previous node) is as follows

We use a static variable n.
1) We call function recursively. when we reach end of list we set n to 0
2) As each stack frame is popped out, n is incremented.
3) When n becomes equal to k, it is the kth node from end of list and we return it
4) When the next stack frame is encountered (in the next call) n becomes k+1, and we have found our previous node of kth node and we set our reference parameter prevnode to this.
5) In subsequent function returns, we return the same kth node.

 #include<stdio.h>  
#include<stdlib.h>
 struct node  
 {  
   int value;  
   struct node *next;   
 };  
 typedef struct node * NODEPTR;  

 NODEPTR create_node(int value)  
 {  
   NODEPTR temp = (NODEPTR) malloc(sizeof(struct node));  
    temp->next = NULL;  
   temp->value = value;  
   return temp;  
 } 

 NODEPTR append_node(NODEPTR head, NODEPTR newnode)  
 {  
    NODEPTR temp = head;
    if(temp==NULL)
      return newnode;
    while(temp->next !=NULL)
	temp = temp->next;
    temp->next = newnode;
    return head;  
 }  
 void display_nodes(NODEPTR head)  
 {  
   NODEPTR temp = head;//redundant 
   while (temp!= NULL)  
   {  
     printf("%d -----",temp->value);  
     temp = temp->next;  
   }  
   printf("\n");
 } 
 NODEPTR create_list(int numnodes)
 {
   NODEPTR head = NULL;
   while(numnodes--)
  {
      int value;  
      NODEPTR newnode;  
      printf("node value=");  
      scanf("%d",&value);  
      newnode = create_node(value);  
      head = append_node(head,newnode);   
    }
     return head;
} 

NODEPTR find_kth_node(NODEPTR nd,NODEPTR *prevnd,int k)
{
    static int n=0;
    static int reachedEnd = 0;
    if(nd !=NULL )
    {  
        NODEPTR temp = find_kth_node(nd->next,prevnd,k);
        /*recursive call*/
        if(reachedEnd)        
	    n++;
        if(k==n)
           return nd;
        if(n==k+1)
         /*previous of kth node*/
            *prevnd = nd;
        if(n<k)
            return NULL;
        return temp; 
    }
    else
        reachedEnd=1;
}
 
NODEPTR delfirstnode(NODEPTR head)
{
	NODEPTR temp = head;
	head = head->next;
	free(temp);
	return head;
}
NODEPTR delete_node(NODEPTR dnode,NODEPTR prev)
{
	prev->next = dnode->next;
	free(dnode);
}
 int main()  
 {  
     NODEPTR head;  
     NODEPTR delnode,prevnode;  
     int numnodes,i;  
     prevnode = NULL;
     printf("Enter number of nodes:");
     scanf("%d",&numnodes);
     head = create_list(numnodes);
     printf("k=");
     scanf("%d",&i);
     delnode = find_kth_node(head,&prevnode,i);
     if(delnode!=NULL)
    {
         if(prevnode)
             printf("kth node is %d prevnode is %d\n",delnode->value,prevnode->value);
         if(prevnode==NULL)
              head = delfirstnode(head);
         else
              delete_node(delnode,prevnode);         
         display_nodes(head);
      }
     else
         printf("There are not %d nodes in the list",i);
}

39. Write a function to print the frequency of a given number in a linked list.

 int frequency(NODEPTR head, int num)
 {
   int c =0;  
   while(head)  
  { 
      if(head->val==num)
         c++;
      head = head->next;
   }
   return c;
}

40. Write a program to add a new node to the front of doubly linked list and to append a node to list.

When we add a node before the head, these three things should happen
1) prev link of head should be newnode
2) next link of newnode should be head
3) head should be set to newnode

When we append a node to doubly linked list
a)If list is empty return newnode
b)Find last node of DLL - this step is not needed if you maintain tail of list.
c)lastnode->next = newnode
d)newnode->prev = lastnode
e) tail = newnode

#include<stdio.h>  
#include<stdlib.h>
 struct node  
 {  
   int n;  
   struct node *next;  
   struct node *prev;  
 };  
 typedef struct node * NODEPTR;  
 NODEPTR create_node(int value);   
 void display_nodes(NODEPTR head);   

 NODEPTR insert_before_head(NODEPTR head, NODEPTR newnode)  
 {  
    newnode->next = head;  
    if(head!=NULL)  
    {  
      head->prev = newnode;  
    }  
    head = newnode;  
    return head;  
 } 
 NODEPTR create_node(int value)  
 {  
   NODEPTR temp = (NODEPTR) malloc(sizeof(struct node));  
   temp->prev = temp->next = NULL;  
   temp->n = value;  
   return temp;  
 } 
 void display_nodes(NODEPTR head)  
 {  
   NODEPTR temp = head; 
   while (temp!= NULL)  
   {  
     printf("%d-->",temp->n);  
     temp = temp->next;  
   }  
 }  
 void display_reverse(NODEPTR tail)  
 {  
   NODEPTR temp = tail; 
   while (temp!= NULL)  
   {  
     printf("%d-->",temp->n);  
     temp = temp->prev;  
   }  
 }  
NODEPTR append(NODEPTR tail,int val)
{
   NODEPTR newnode = create_node(val);
   if(tail == NULL)/*list is emptyt*/
      return newnode;
   
   tail->next = newnode;
   newnode->prev = tail;
   tail = newnode;
   return tail;
} 

 int main()  
 {  
     NODEPTR head,tail;  
     NODEPTR newnode;  
     int numnodes,i;  
     //initialize head and tail. 
     head = tail = NULL;  
     printf("Number of nodes = ");  
     scanf("%d",&numnodes);      
     for( i=0;i<numnodes;i++)  
     {  
       int value;  
       NODEPTR newnode;  
       printf("node value=");  
       scanf("%d",&value);   
       tail = append(tail,value);
       if(head==NULL)  
       {  
          head = tail;
       }  
     }   
     printf("Value to be inserted before head");
     scanf("%d",&i);
     head = insert_before_head(head,create_node(i));    
     printf("The doubly linked list is ");  
     display_nodes(head); 
     printf("In reverse");
     display_reverse(tail);      
 }

LinkedList Questions