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 ## 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.

## S

### To fold a linked list following steps are followed

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

### To fold a linked list following steps are followed

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. ## M

4. CURR=CURR->NEXT
6. END IF
9. CURR=CURR->NEXT
11. END IF  & WHILE

## M

4. CURR=CURR->NEXT
6. END IF
9. CURR=CURR->NEXT
11. END IF  & WHILE

## 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);
struct node* newNode(int data);

int main(void)//main method.
{
int n,k;
cin>>n;
int data;
for(int i=0;i<n;i++) { cin>>data[i];
}

for (int i = n-1; i >= 0; i--)

return 0;
}

{
struct node* newNode = (struct node*)malloc(sizeof(struct node));
newNode->data = data;
}
{
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;
}
slow->next = NULL;//slow pointer will be at middle position

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

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

curr = curr->next;
}

curr = curr->next;
}
}

}
//function for reversing the List
{
node *prev = NULL, *curr = *head, *next;

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

}```
```Output:
5
14
56
25
31
54

Linked List Data: 14 56 25 31 54