#include <stdio.h>
//#include "stdafx.h"
#include <malloc.h>


struct node
{
	int data;
	struct node *link;
};

void addFirst(struct node **q, int data)
{
	struct node *ptr = (struct node*)malloc(sizeof(struct node));
	ptr->data = data;
	ptr->link = *q;
	*q = ptr;
}

void printList(struct node *head)
{
	struct node *temp = head;

	while (temp != NULL)
	{
		printf("%d", temp->data);
		printf("\n");
		temp = temp->link;
	}

}

void bubbleSort(struct node *head)
{
	struct node *p, *q, *r, *s, *temp;
	s = NULL;

	while(s != head->link)
	{
		{
			r = p = head;
			q = p->link;
			while (p != s)
			{
				if (p->data > q->data)
				{
					if (p == head)
					{
						temp = q->link;
						q->link = p;
						p->link = temp;

						head = q;
						r = q;
					}
					else
					{
						temp = q->link;
						q->link = p;
						p->link = temp;

						r->link = q;
						r = q;
					}

				}
				else
				{
					r = p;
					p = p->link;
				}
				q = p->link;
				if (q == s)
					s = p;
			}
		} }
}


int main()
{
	struct node *a = NULL;
	addFirst(&a, 5);
	addFirst(&a, 20);
	addFirst(&a, 4);
	addFirst(&a, 30);
	addFirst(&a, 20);
	addFirst(&a, 10);
	addFirst(&a, 9);
	addFirst(&a, 7);

	printf("Initial list: \n");
	printList(a);
	bubbleSort(a);
	printf("Sorted list: \n");
	printList(a);

    return 0;
}