C Program to sort a linked list


Levels of difficulty: / perform operation:

Linked list is a data structure in which the objects are arranged in a linear order. In this program, we sort the list elements in ascending order.



C Program

#include <stdio.h>
#include <stdlib.h>
#define NULL 0
struct linked_list {
	int number;
	struct linked_list *next;
};
typedef struct linked_list node;
main () {
	int n;
	node *head = NULL;
	void print(node *p);
	node *insert_Sort(node *p, int n);
	printf("Input the list of numbers.\n");
	printf("At end, type -999.\n");
	scanf("%d",&n);
	while(n != -999) {
		if(head == NULL)       
		/* create 'base' node */ {
			head = (node *)malloc(sizeof(node));
			head ->number = n;
			head->next = NULL;
		} else    
		/* insert next item */ {
			head = insert_Sort(head,n);
		}
		scanf("%d", &n);
	}
	printf("\n");
	print(head);
	print("\n");
}
node *insert_Sort(node *list, int x) {
	node *p1, *p2, *p;
	p1 = NULL;
	p2 = list;
	/* p2 points to first node */
	for ( ; p2->number < x ; p2 = p2->next) {
		p1 = p2;
		if(p2->next == NULL) {
			p2 = p2->next;
			/* p2 set to NULL */
			break;
			/* insert new node at end */
		}
	}
	/* key node found */
	p = (node *)malloc(sizeof(node));
	/* space for new node */
	p->number = x;
	/* place value in the new node */
	p->next = p2;
	/* link new node to key node */
	if (p1 == NULL)
	  list = p;
	/* new node becomes the first node */ else
	  p1->next = p;
	/* new node inserted after 1st node */
	return (list);
}
void print(node *list) {
	if (list == NULL)
	  printf("NULL"); else {
		printf("%d-->",list->number);
		print(list->next);
	}
	return;
}





Quantitative Aptitude
Reasoning
Programming
Interview