linked list operations

1/* Given a Singly linked list L0->L1->L2->L3->L4->.......;Write a program to rearrange the nodes in the list so that the newly
2    formed list is :L0->Ln->L1->Ln-1->L2->Ln-2->.....
3    Sample input: 1 2 3 4 5 6
4    Sample output:1 6 2 5 3 4
5*/
6
7#include<iostream>
8using namespace std;
9struct node
10{
11    int data;
12    node* next;
13};
14node *head=new node;
15node *head1,*head2;
16void dummy(int s)
17{
18    node *temp=new node;
19    temp->data=s;
20    temp->next=NULL;
21    head=temp;
22}
23void insert_ll(int k)//Inserting into the list
24{
25    node* temp=new node;
26    temp->data=k;
27    temp->next=NULL;
28    if(head==NULL)
29    {
30        head=temp;
31    }
32    else
33    {
34        node* ptr=head;
35        while(ptr->next!=NULL)
36        {
37            ptr=ptr->next;
38        }
39        ptr->next=temp;
40    }
41}
42void split()//Splitting the list into two halves
43{
44    node* slow=head;
45    node* fast=head->next;
46    while(fast&&fast->next)
47    {
48        slow=slow->next;
49        fast=fast->next->next;
50    }
51    head1=head;
52    head2=slow->next;
53    slow->next=NULL;
54}
55void reversing()//Reversing the list
56{
57    node* current=head2;
58    node* prev=NULL;
59    node*temp;
60    while(current)
61    {
62        temp=current->next;
63        current->next=prev;
64        prev=current;
65        current=temp;
66    }
67    head2=prev;
68}
69void merge__ll()//Merging the list
70{
71    dummy(0);
72    node*current=head;
73    while(head1||head2)
74    {
75        if(head1)
76        {
77            current->next=head1;
78            current=current->next;
79            head1=head1->next;
80        }
81        if(head2)
82        {
83            current->next=head2;
84            current=current->next;
85            head2=head2->next;
86        }
87    }
88    head=head->next;
89}
90void print()//Printing the list
91{
92    node*temp =head;
93    while(temp!=NULL)
94    {
95        cout<<temp->data<<" ";
96        temp=temp->next;
97    }
98    cout<<endl;
99}
100int main()
101{
102    head=NULL;
103    int n;
104    cout<<"Enter the size:"<<endl;//for this question we will consider size though linked list is dynamic and does not have a fixed size
105    cin>>n;
106    int x;
107    cout<<"enter the elements:"<<endl;
108    for(int i=0;i<n;i++)
109    {
110        cin>>x;
111        insert_ll(x);
112    }
113    cout<<"Linked list without the modification is:";
114    print();
115    split();
116    reversing();
117    merge__ll();
118    print();
119    return 0;
120}
121

1// the function is returning the head of the singly linked list
2Node insertAtEnd(Node head, int val)
3{
4    if( head == NULL ) // handing the special case
5    {
6        newNode = new Node(val)
7        head = newNode
8        return head
9    }
10    Node temp = head
11    // traversing the list to get the last node
12    while( temp.next != NULL )
13    {
14        temp = temp.next
15    }
16    newNode = new Node(val)
17    temp.next = newNode
18    return head
19}