// 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);
	}
}
4
Contributors
4
Replies
5
Views
10 Years
Discussion Span
Last Post by virusfree
0

excellent work. Only two suggestions:
1. fflush(stdin); -- fflush() is guarenteed to only work with output streams. Some compilers allow it for input streams, but that is compiler-specific and will not work on many compilers.

2. In the loop that gets keyboard input you should add a prompt to that the program does not appear to be hung up and doing nothing

for(index = 0;index < numNodes;index++)
	{
		printf("\rEnter item number %d ...", index);
		scanf("%d",&tempArray[index]);
	}
0

The behaviour of fflush( stdin ) is always undefined whatever be the compiler -- its just that some compilers let you get away with it.

And as far as sorting the linked list is concerned, there is another simple way of doing it -- sort the list as and when the data is entered so that the list is always in sorted form. Before adding each data element, make a search through the entire llist to find where that data exactly belongs to so that it can be inserted at the appropriate position.

Thank you.

0

to ~s.o.s~

ok, but what if you are given the option of only sorting the list and not creating it?, I wrote CreateLinkedList only as an addon to test it.

Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.