Sorting a Linked List

// SampleLinkedListSortTest.cpp : Defines the entry point for the console application.
//

#include <stdio.h>
#include <stdlib.h>

typedef struct linkedList
{
	int data;
	struct linkedList *next;		
}linkedListNode;

linkedListNode* CreateLinkedList(linkedListNode **head,int tempArray[],int maxLevel);
void M_Sort(linkedListNode **head);
linkedListNode* Merge(linkedListNode **leftHead,linkedListNode **riteHead);
void SplitLinkedList(linkedListNode *head,linkedListNode **leftHead,linkedListNode **riteHead);
void DisplayList(linkedListNode *head);

linkedListNode *head;

int main()
{
	int numNodes = 0;
	int index = 0;
	int *tempArray = NULL;		

	printf("\nCreating the linked list...\n");
	//numNodes -> no of nodes in the linked list
	numNodes = 7;
	tempArray = (int *)calloc(numNodes,sizeof(int));
	if(!tempArray)
	{
		printf("\nMemory allocation for dynamic array failed ...\n");
		return 0;
	}
	fflush(stdin);
	fflush(stdout);

	for(index = 0;index < numNodes;index++)
	{
		scanf("%d",&tempArray[index]);
	}
	
	if(!CreateLinkedList(&head,tempArray,numNodes))
	{
		printf("\nLinked list creation unsuccessful..\n\n exiting..\n");
		free(tempArray);
                  return 0;
	}
	//we don't need the temp array anymore
	free(tempArray);
	
	M_Sort(&head);
	printf("\nPrinting Sorted Linked List ...\n");
	DisplayList(head);
	return 0;
}

/* This Function creates the linked list (recursively)*/
linkedListNode* CreateLinkedList(linkedListNode **head,int tempArray[],int maxLevel)
{
	static int currentLevel = 0;
	linkedListNode *temp;

	if(currentLevel >= maxLevel)
	{
		return NULL;
	}
	temp = (linkedListNode *)malloc(sizeof(linkedListNode));
	if(!temp)
	{
		printf("\nMemory allocation for linkedListNode creation failed ..\n");
		return NULL;			
	}		
	temp->data = tempArray[currentLevel];
	currentLevel++;
	temp->next = CreateLinkedList(head,tempArray,maxLevel);
	currentLevel--;

	if(currentLevel == 0)
	{
		*head = temp;
	}
	return temp;
}

/* This function does the MergeSort */
void M_Sort(linkedListNode **head)
{
	linkedListNode *leftHead = NULL;
	linkedListNode *riteHead = NULL;

	if(!head)
	{
		return;
	}
	if(!*head)
	{
		return;
	}
	if(!(*head)->next)
	{
		return;
	}
	leftHead = *head;
	riteHead = *head;
	//Keep splitting the list in the middle
	SplitLinkedList(*head,&leftHead,&riteHead);
	
	M_Sort(&leftHead);
	M_Sort(&riteHead);
	//head now points to the merged list 
	*head = Merge(&leftHead,&riteHead);
}

// This function Merges 2 sorted linked lists into a sorted single list
linkedListNode* Merge(linkedListNode **leftHead,linkedListNode **riteHead)
{
	//We need 2 pointers in both the lists to merge the nodes
	linkedListNode *leftFront = NULL;
	linkedListNode *leftRear = NULL;
	linkedListNode *riteFront = NULL;
	linkedListNode *riteRear = NULL;

	//Do the Null Pointer Checks
	if(!leftHead)
	{
		return NULL;
	}
	if(!*leftHead)
	{
		return NULL;
	}
         if(!riteHead)
	{
		return *leftHead;
	}
	if(!*riteHead)
	{
		return *leftHead;
	}
	//Initialize the pointers in left, rite Lists
	leftFront = *leftHead;
	leftRear = NULL;
	riteFront = *riteHead;
	riteRear = NULL;
	
	// If there is only one node in both the lists
	// then simply do a check and merge the nodes
	if(leftFront->next == NULL && riteFront->next == NULL)
	{
		if(leftFront->data < riteFront->data)
		{
			leftFront->next = riteFront;
		}
		else
		{
			riteFront->next = leftFront;
			*leftHead = riteFront;
		}
		return *leftHead;
	}

	//If either of the list has more than 1 node
	/*The idea here is to have a riteFront pointer as a checkpoint
	  and keep moving the leftFront pointer until you reach a node
	  on the rite list  whose value is > leftFront->data, then merge at that node using
	  the rear pointers */
	while(leftFront != NULL && riteFront != NULL)
	{
		//keep traversing until you hit a node on the left list
		//such that its value is > the value on rite list
		while(leftFront != NULL && leftFront->data < riteFront->data)
		{
			leftRear = leftFront;
			leftFront = leftFront->next;
		}
		// check for NULL pointers
		if(leftFront != NULL && riteFront != NULL)
		{
			/*If the rear pointer is pointing to NULL it indicates
			  the data on the ritelist to merge is supposed to get 
			  to the beginning of the merged list */
			if(leftRear == NULL)
			{
				riteRear = riteFront;
				riteFront = riteFront->next;
				leftRear = riteRear;
				leftRear->next = leftFront;
				*leftHead = riteRear;
				if(!riteFront)
				{
					break;
				}
			}
			//Else the node is supposed to merged in between / end of the merged list
			else
			{
				riteRear = riteFront;
				riteFront = riteFront->next;
				leftRear->next = riteRear;
				leftRear = leftRear->next;
				leftRear->next = leftFront;
				if(!riteFront)
				{
					break;
				}
			}
			if(leftFront->data < riteFront->data)
			{
				leftRear = leftFront;
				leftFront = leftFront->next;
			}
			else
			{
				continue;
			}
		}
	}// end of while

	if(leftFront == NULL && riteFront != NULL)
	{
		leftRear->next = riteFront;
	}
	return *leftHead;
}

/*This function splits the given list into 2 at the middle, 
  leftHead points to left list and riteHead to rite */
void SplitLinkedList(linkedListNode *head,linkedListNode **leftHead,linkedListNode **riteHead)
{
	linkedListNode *leftTemp = NULL;		
	linkedListNode *riteTemp = NULL;
	if(!head)
	{
		return;
	}
	if(!leftHead || !riteHead)
	{
		return;
	}
	if(!*leftHead || !*riteHead)
	{
		return;
	}
	leftTemp = head;
	riteTemp = head;

	if(!(riteTemp->next))
	{
		*riteHead = NULL;
		return;
	}
	while(riteTemp->next != NULL)
	{
		riteTemp = riteTemp->next;
		if(riteTemp->next != NULL)
		{
			leftTemp = leftTemp->next;
			riteTemp = riteTemp->next;
		}
		else
		{
			*riteHead = leftTemp->next;
			leftTemp->next = NULL;
		}
	}
	if(*riteHead == head)
	{
		*riteHead = leftTemp->next;
		leftTemp->next = NULL;
	}
	return;
}

/* This function displays the linked list */
void DisplayList(linkedListNode *head)
{
	for(; head!= NULL;head = head->next)
	{
		printf("%d\n",head->data);
	}
}