# Solution for Sort List

• #include<iostream>
using namespace std;

struct node
{
int val;
struct node *next;
};

void FrontBackSplit(struct node* source,
struct node** frontRef, struct node** backRef) {
struct node* fast;
struct node* slow;
if (source == NULL || source->next == NULL) { // length < 2 cases
*frontRef = source;
*backRef = NULL;
}
else {
slow = source;
fast = source->next;
while (fast != NULL) {
fast = fast->next;
if (fast != NULL) {
slow = slow->next;
fast = fast->next;
}
}
// 'slow' is before the midpoint in the list, so split it in two
// at that point.
*frontRef = source;
*backRef = slow->next;
slow->next = NULL;
}
}

struct node* SortedMerge(struct node* a, struct node* b)
{
struct node* result;

``````if (a == NULL)
{
return b;
}
else if (b == NULL)
{
return a;
}
else
{
if (a->val < b->val)
{
result = a;
result->next = SortedMerge(a->next, b);
}
else
{
result = b;
result->next = SortedMerge(a, b->next);
}
}

return result;
``````

}

struct node
a;
struct node* b;
// Base case -- length 0 or 1
return;
}
// We could just as well use AlternatingSplit()
MergeSort(&a); // Recursively sort the sublists
MergeSort(&b);
*headRef = SortedMerge(a, b); // answer = merge the two sorted lists together
}

void insertList(struct node** headref, int data)
{
struct node * newNode = new node();
newNode->val = data;
newNode->next = NULL;

``````if (*headref == NULL)
{
}
else
{
while (current->next != NULL)
{
current = current->next;
}
current->next = newNode;
}
``````

}

{
while (current != NULL)
{
cout << current->val << "->";
current = current->next;
}

``````cout <<"NULL" << endl;
``````

}

int main()
{

``````insertList(&head, 5);