Inserting an element into sorted linked list

Given a sorted linked list write a program to insert data into it’s correct position.

For example consider the following linked list

1 -> 3 -> 4 -> 5

Inserting 2 should change the list to

1 -> 2 -> 3 -> 4 -> 5

Inserting 0 should change it to

0 -> 1 -> 2 -> 3 -> 4 ->5

Inserting 6 should change it to

0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6.

The three examples indicate three different cases to be considered while inserting into a sorted linked list.

Case 1: List can be empty or new element is added as the first element

Case 2: New element can be inserted anywhere in the middle of the linked list

Case 3: New element is added as the last element.

The following diagram illustrates the insert process.

In the following C++ program case 1 is handled in one block and case 2 and 3 are handled in the last block.

	#include <iostream>

	using namespace std;

	struct Node
	{
	int data;
	Node * next;
	};

	void Print(Node * head)
	{
	while ( head )
	{
	cout<< head->data << " ";
	head = head->next;
	}
	cout << endl;
	}

	Node * SortedInsert(Node * head, int d )
	{
	Node * newNode = new Node();
	newNode->data = d;

	//special case: newnode to be added as first node
	if( head == NULL \|\| head->data >= d)
	{
	newNode->next = head;
	head = newNode;
	return head;
	}

	Node *ptr = head;
	Node *prev = NULL;

	while ( ptr != NULL && ptr->data < d )
	{
	prev = ptr;
	ptr = ptr->next;
	}

	newNode->next = ptr;
	prev->next = newNode;

	return head;
	}

	int main()
	{
	Node * head = NULL;
	head = SortedInsert(head, 3);
	head = SortedInsert(head, 2);
	head = SortedInsert(head, 1);
	head = SortedInsert(head, 4);
	head = SortedInsert(head, 6);
	head = SortedInsert(head, 5);
	Print(head);

	return 0;
	}

by GitHub