#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
Login/Signup to comment