C Program for Folding a Linked List

July 16, 2020

C Program for folding a linked list

Learn how to fold a linked list

Today we learn how to write a code in C Program for fold a linked list, it is a way to divide the linked list and merge the two end of the linked list that make a fold . In below sections, we will learn steps and coe to perform the task.
For example :- Input : 10 12 3 14
Output : 10 14 12 3 (after folding linked list)

Steps required for folding a linked list :-

fold a linked list in c
  • Firstly, Initialize a linked list.
  • Then find the middle point using two pointers at different speeds through the sequence of values until they both have equal values.
  •  Divide the linked list into two halves using these pointer named as slow and fast, then find middle.
  • Now reverse the second half of the linked list.
  • At last alternate merge of first and second halves.
  • Print the fold linked list.
Structure of in linked list 
struct node
{
int data;
struct node *next;
};
C Program for fold a linked list

Algorithm for a C Program for folding a linked list :-

  • MAKE A WHILE LOOP ( HEAD NODE 1 || HEAD NODE 2 )
  • IF ( HEAD NODE 1 )
  • THEN CURRENT →NEXT POINTER = HEAD NODE 1
  • CURRENT =CURRENT →NEXT POINTER
    HEAD NODE 1=HEAD NODE 1→ NEXT POINTER
  • END OF IF LOOP
  • ELSE ( HEAD NODE 2 )
  • THEN CURRENT→ NEXT POINTER = HEAD NODE 2
  • CURRENT = CURRENT→ NEXT POINTER
  • HEAD NODE 2 =HEAD NODE 2 →NEXT POINTER
  • END ELSE AND WHILE LOOP
    HEAD=HEAD → NEXT POINTER

C Program for folding a linked list :-

#include <stdio.h>
#include <stdlib.h>
struct node         // structure of the node
{
  int data;
  struct node *next;
};
void reverse_list (struct node **head)       //function for reverse list
{
  struct node *prev = NULL, *curr = *head, *next;
  while (curr)
    {
      next = curr->next;
      curr->next = prev;
      prev = curr;
      curr = next;
    }

  *head = prev;
}

void create (struct node **head, int data)          //function for create list
{
  struct node *new_n;
  new_n = (struct node *) malloc (sizeof (struct node));
  new_n->data = data;
  new_n->next = *head;
  *head = new_n;

}

void print (struct node *head)              //function for display list
{
  struct node *ptr = head;
  while (ptr)
    {
      printf ("%d\n", ptr->data);
      ptr = ptr->next;
    }
}

struct node *newNode (int data)
{

  struct node *new_n;
  new_n = (struct node *) malloc (sizeof (struct node));
  new_n->data = data;
  new_n->next = NULL;
  return new_n;
}

void fold (struct node **head)          //final function for fold a linked list
{
  struct node *slow = *head;
  struct node *fast = slow->next;
  struct node *curr;
  while (fast && fast->next)
    {
      slow = slow->next;
      fast = fast->next->next;
    }
  struct node *head1 = *head;
  struct node *head2 = slow->next;
  slow->next = NULL;

  reverse_list (&head2);

  *head = newNode (0);

  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;
}

int main ()                 //main function of the code
{
  struct node *head = NULL;
  int n, k, i;
  int data[100];
  printf ("Enter size of link list :-\n");
  scanf ("%d", &n);
  printf ("Enter data for link list:-\n");
  for (i = 0; i < n; i++)
    {
      scanf ("%d", &data[i]);
    }
  for (i = n - 1; i >= 0; i--)           //creating Link list
    {
      create (&head, data[i]);
    }
  printf ("Link list data:-");
  print (head);
  fold (&head);
  printf ("Link list data after fold :-");
  print (head);
  return 0;
}
Output :-
Enter size of link list :-
5
Enter data for link list:-
12
4
51
20
68
Link list data:-
12
4
51
20
68
Link list data after fold :-
12
68
4
20
51

Explore these topics to learn more :-

Singly Linked
list

   Doubly Linked List

Circular Linked List