Please login

Prime

Prepinsta Prime

Video courses for company/skill based Preparation

(Check all courses)
Get Prime Video
Prime

Prepinsta Prime

Purchase mock tests for company/skill building

(Check all mocks)
Get Prime mock

C++ program to fold a linked list

Program to fold a link list in C++

How to fold a linked list?

Folding a linked list is like joining the two end of the linked list, and merging them together. In this article, we will learn that what does Folding a Linked List means, and what steps and algorithm we need to follow to perform the following task. Let’s see how to code a C++ Program for folding a Linked List.

Steps to write a C++ program to fold a linked list

S

T

E

P

S

To fold a linked list following steps are followed

  1. Define the linked list.
  2. In the main method call all the method you have declared with input/output statement you want to use.
  3. In the method fold multiple process are going on.
  4. First we are finding middle of the linked using slow and fast pointer trick.
  5. Now we will divide the linked list into two half
  6. Second we are reversing the linked list from middle to tail i.e. second half of the list.
  7. Later we will print each element of both the list one by one.

S

T

E

P

S

To fold a linked list following steps are followed

  1. Define the linked list.
  2. In the main method call all the method you have declared with input/output statement you want to use.
  3. In the method fold multiple process are going on.
  4. First we are finding middle of the linked using slow and fast pointer trick.
  5. Now we will divide the linked list into two half
  6. Second we are reversing the linked list from middle to tail i.e. second half of the list.
  7. Later we will print each element of both the list one by one.

How to construct a linked list ?

class Node  

    int data; 
    Node *next; 
}; 

Using following set of codes in our program we can construct linked list.

C++ program to fold a linked list

Algorithm to fold a linked list in C++

A

L

G

O

R

I

T

H

M

  1. WHILE(HEAD1||HEAD2)
  2. IF(HEAD1)
  3. CURR->NEXT=HEAD1
  4. CURR=CURR->NEXT
  5. HEAD1=HEAD1->NEXT
  6. END IF
  7. IF(HEAD2)
  8. CURR->NEXT=HEAD2
  9. CURR=CURR->NEXT
  10. HEAD2=HEAD2->NEXT
  11. END IF  & WHILE
  12. HEAD=HEAD->NEXT

A

L

G

O

R

I

T

H

M

  1. WHILE(HEAD1||HEAD2)
  2. IF(HEAD1)
  3. CURR->NEXT=HEAD1
  4. CURR=CURR->NEXT
  5. HEAD1=HEAD1->NEXT
  6. END IF
  7. IF(HEAD2)
  8. CURR->NEXT=HEAD2
  9. CURR=CURR->NEXT
  10. HEAD2=HEAD2->NEXT
  11. END IF  & WHILE
  12. HEAD=HEAD->NEXT

Program to fold a linked list in C++

#include <iostream> 
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 print(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: ";	
    print(head);
    
	fold(&head);
	cout<<"\nLinked list after folding\nLinked List Data: ";
	print(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 print(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; 
}
Output:
Enter size of linked list
5
Enter linked list data 
14
56
25
31
54

Linked List Data: 14 56 25 31 54 
Linked list after folding
Linked List Data: 14 54 56 31 25