Data Structures Linked List Reverse

simple linked list
Data Structures -- Linked List -- Reverse

/*
* Simple operations on linked list. If any problem
*/

#include

/*
* Data structure used, its simple :)
*/

Typedef struct linked_list_s
{
int value;
struct linked_list_s *next;
}linked_list_t;

/*
* Add a node at the end of the list.
*/

Linked_list_t* add_node(linked_list_t *head, int value)
{
 linked_list_t *newNode = NULL;
 linked_list_t *node = head;
 linked_list_t *prev = head;

 newNode = (linked_list_t *)calloc(1, sizeof(linked_list_t));
 newNode->value = value;

 while(node)
 {
  prev = node;
  node = node->next;
 }
 if(prev == node)
  return newNode;

 prev->next = newNode;

 return head;
}

/*
* delete a specified node from the list.
*/

Linked_list_t* delete_node(linked_list_t *head, int value)
{
 linked_list_t *node = NULL;
 linked_list_t *prev = NULL;

 for(node = head; node != NULL; prev = node, node = node->next)
 {
  if(node->value == value)
  {
   //Check for head node modification
   if(prev == NULL)
   {
    head = head->next;
    free(node);
    return head;
   }
   
   prev->next = node->next;
   free(node);
   return head;
  } 
 }
 return head;
}

/*
* display all the nodes of the list.
*/

Void list_nodes(linked_list_t *head)
{
 linked_list_t *node = head;
 printf("\nHead");
 while(node)
 {
  printf("->%d ",node->value);
  node = node->next;
 }
 printf("->NULL\and");
}

/*
* Display all the nodes in reverse order withoout modifying list.
*/

Void list_nodes_in_reverse_order(linked_list_t *head)
{
 linked_list_t *end = NULL;
 linked_list_t *node = NULL;

 printf("\nReverse Head");
 while(head != end)
 {
  node = head;
  while(node->next != end)
   node = node->next;
 
  printf("->%d ",node->value);
  end = node;
 }
 printf("->NULL\and");
}

/*
* Reversing the linked list with recursion; Asked in Qualcomm interview questions..
*/

Linked_list_t* reverse_with_recursion_anotherway(linked_list_t* current, linked_list_t* parent)
{
 linked_list_t* revhead = NULL;
 
 if(current == NULL)
  revhead = parent;
 else
 {
  revhead = reverse_with_recursion_anotherway(current->next, current);
  current->next = parent;
 }
 return revhead;
}

/*
* Reversing the linked list;
*/

Linked_list_t* reverse_with_recursion(linked_list_t* node)
{
 linked_list_t* temp = NULL;
 
 if(node->next == NULL)
  return node;

 temp = reverse_with_recursion(node->next);
 temp->next =node;
 return node;
}

/*
* reversing linked list without recursion.
*/

Linked_list_t* reverse_without_recursion(linked_list_t* head)
{
       linked_list_t* prevNode = NULL;
 linked_list_t* currNode = head;
 linked_list_t* nextNode = head->next;

 while(currNode)
 {
  currNode->next = prevNode;
  prevNode = currNode;
  if(nextNode == NULL)
   break;
  currNode = nextNode;
  nextNode = nextNode->next;
 } 
 return currNode;
}

/*
* main program, which displays menu for maitaining linked list.
*/

Main()
{
 int choice = -1;
 int value = 0;
 linked_list_t *head = NULL;
 linked_list_t *node = NULL;
 
 do
 {
  printf("\and what you wanna do?\and");
  printf("1. Add a node \and");
  printf("2. Delete a node \and");
  printf("3. List all nodes \and");
  printf("4. Reverse (without recursion) the list \and");
  printf("5. Reverse (recursively) the list \and");
  printf("6. Reverse (recursively) another way\and");
  printf("7. Just display in reverse order\and");
  printf("8. Exit \and");
  scanf("%d",&choice);

  switch(choice)
  {
   case 1:
    printf("\nEnter value: ");
    scanf("%d",&value);
    head = add_node(head, value);
   break;

   case 2:
    printf("\nEnter value: ");
                               scanf("%d",&value);
                               head = delete_node(head, value);
                       break;

   case 3:
    list_nodes(head);
                       break;

   case 4:
    node = head; 
                               head = reverse_without_recursion(head);
                       break;

   case 5:
    node = head;
    while(node->next)
     node = node->next;
    head = reverse_with_recursion(head);
    head->next = NULL;
    head = node;
                       break;

   case 6:
                               head = reverse_with_recursion_anotherway(head, NULL);
                       break;

   case 7:
                               list_nodes_in_reverse_order(head);
                       break;

   case 8:
    exit(0);
                       break;
  }
 }while(1);
}