WAP for Sorting Doubly Linked List

/* Program to reverse a doubly linked list */
#include
#include

/* a node of the doubly linked list */
struct node
{
int data;
struct node *next;
struct node *prev;
};


/* UTILITY FUNCTIONS */
/* Function to insert a node at the beginging of the Doubly Linked List */
void push(struct node** head_ref, int new_data)
{
/* allocate node */
struct node* new_node =
(struct node*) malloc(sizeof(struct node));

/* put in the data */
new_node->data = new_data;

/* since we are adding at the begining,
prev is always NULL */
new_node->prev = NULL;

/* link the old list off the new node */
new_node->next = (*head_ref);

/* change prev of head node to new node */
if((*head_ref) != NULL)
(*head_ref)->prev = new_node ;

/* move the head to point to the new node */
(*head_ref) = new_node;
}


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

/* Base cases */
if (a == NULL)
return(b);
else if (b==NULL)
return(a);

/* Pick either a or b, and recur */
if (a->data <= b->data)
{
result = a;
result->next = SortedMerge(a->next, b);
}
else
{
result = b;
result->next = SortedMerge(a, b->next);
}
return(result);
}

int Length(struct node* head)
{
int count = 0;
struct node* current = head;
while (current != NULL)
{
count++;
current=current->next;
}
return(count);
}
// to split list in to two equal part using lenth function
void FrontBackSplit(struct node* source,struct node** frontRef, struct node** backRef)
{
int len = Length(source);
int i;
struct node* current = source;

if (len < 2) {
*frontRef = source;
*backRef = NULL;
}
else {
int hopCount = (len-1)/2; //(figured these with a few drawings)
for (i = 0; icurrent = current->next;
}
// Now cut at current
*frontRef = source;
*backRef = current->next;
current->next = NULL;
}
}


/* sorts the linked list by changing next pointers (not data) */
void MergeSort(struct node** headRef)
{
struct node* head = *headRef;
struct node* a;
struct node* b;

/* Base case -- length 0 or 1 */
if ((head == NULL) || (head->next == NULL))
{
return;
}

/* Split head into 'a' and 'b' sublists */
FrontBackSplit(head, &a, &b);

/* Recursively sort the sublists */
MergeSort(&a);
MergeSort(&b);

/* answer = merge the two sorted lists together */
*headRef = SortedMerge(a, b);
}




/* Function to print nodes in a given doubly linked list
This function is same as printList() of singly linked lsit */

void printList(struct node *node)
{
while(node!=NULL)
{
printf("%d ", node->data);
node = node->next;
}
}

/* Drier program to test above functions*/
int main()
{
/* Start with the empty list */
struct node* head = NULL;

/* Let us create a sorted linked list to test the functions
Created linked list will be 10->8->4->2 */
push(&head, 3);
push(&head, 1);
push(&head, 2);
push(&head, 2);
push(&head, 1);
push(&head, 3);
push(&head, 1);
push(&head, 2);
push(&head, 2);

printf("\n Original Linked list ");
printList(head);

MergeSort(&head);


printf("\nsorted Doubly Linked list ");
printList(head);


getchar();
}


Run Here https://ideone.com/dESuB