C++ program to fold a linked list

Run

#include<bits/stdc++.h>
using namespace std;
//constructing the structure of a node
struct node
{
  int data;
  struct node *next;
};
//declaring the prototype of the functions that we are going to use
void build (struct node **head, int data);
void display (struct node *head);
struct node *newNode (int data);
void fold (node ** head);
void reverselist (node ** head);

int main (void)			//main method.
{
  int n, k;
  cout<< "Enter size of linked list\n"; cin>>n;
  int data[100];
  cout << "Enter linked list data\n";
  for (int i = 0; i < n; i++) { cin >> data[i];
    }


  struct node *head = NULL;

  //constructing linked list
  for (int i = n - 1; i >= 0; i--)
    build (&head, data[i]);
  cout << "\nLinked List Data: ";
  display (head);

  fold (&head);
  cout << "\nLinked list after folding\nLinked List Data: "; display (head); return 0; } void build (struct node **head, int data) //fuction to build the linked list { struct node *newNode = (struct node *) malloc (sizeof (struct node)); newNode->data = data;
  newNode->next = *head;
  *head = newNode;
}

void display (struct node *head)	//displaying the linked List
{
  struct node *ptr = head;
  while (ptr)
    {
      cout << ptr->data << " "; ptr = ptr->next;
    }
}

struct node *newNode (int data)		//allocating memory to a new node(dummy node)
{
  struct node *newNode = (struct node *) malloc (sizeof (struct node));
  newNode->data = data;
  newNode->next = NULL;
  return newNode;
}

void fold (node ** head)		//function for rearranging the node
{

  node *slow = *head, *fast = slow->next;
  while (fast && fast->next)
    {
      slow = slow->next;
      fast = fast->next->next;
    }
  struct node *head1 = *head;
  struct node *head2 = slow->next;
  slow->next = NULL;		//slow pointer will be at middle position 

  reverselist (&head2);		//reversing second half of the list 


  *head = newNode (0);		// Assign dummy Node 

  node *curr = *head;
  while (head1 || head2)
    {
      if (head1)
	{
	  curr->next = head1;
	  curr = curr->next;
	  head1 = head1->next;
	}

      if (head2)
	{
	  curr->next = head2;
	  curr = curr->next;
	  head2 = head2->next;
	}
    }

  *head = (*head)->next;
}

//function for reversing the List
void reverselist (node ** head)
{
  node *prev = NULL, *curr = *head, *next;

  while (curr)
    {
      next = curr->next;
      curr->next = prev;
      prev = curr;
      curr = next;
    }

  *head = prev;
}