CareerCup

public static void Insert(Node first, int n)
{
    Node temp=new Node(n);
    if(first==null || first.value>n)
    {
        temp.next=first;
        first=temp;
        return;
    }
    while(first.next!=null && first.next.value<n)
        first=first.next;
    temp.next=first.next;
    first.next=temp;
    return;
}

public class SortedLinkedList {
	Node head;
	
	class Node{
		int value;
		Node next;
		public Node(int value) {
			super();
			this.value = value;
			this.next = null;
		}
		
	}
	
	public void add(int value){
		Node newnode = new Node(value);
		if(head == null){
			head = newnode;
			return;
		}
		Node ptr = head;
		Node prev = null;
		while(ptr != null && value > ptr.value){
			prev = ptr;
			ptr = ptr.next;
		}
		if(ptr == head){
			newnode.next = head;
			head = newnode;
			return;
		}
		if(ptr == null){
			prev.next = newnode;
			return;
		}
		newnode.next = ptr;
		prev.next = newnode;
	}
	
	public void print(){
		Node ptr = head;
		if(ptr == null){
			return;
		}
		while(ptr != null){
			System.out.print(ptr.value);
			ptr = ptr.next;
		}
	}
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		SortedLinkedList ll = new SortedLinkedList();
		ll.add(3);
		ll.add(9);
		ll.add(6);
		ll.add(7);
		ll.add(3);
		
		ll.print();
	}

}

void insert(node* &root, int x)
{
    node *start = root;
    node *n = new node(x);
    if (!root)
    {
        root = n;
        return;
    }
    if (root->info > x)
    {
        n->next = root;
        root = n;
        return;
    }
    while ((start->next) && (start->next->info < x))
    {
        start = start->next;
    }
    n->next = start->next;
    start->next = n;
}

Javascript, assuming we have LinkedList class with head property:

LinkedList.prototype.insertNode = function(value){
  var prev = {
    data: null,
    next: this.head
  };
  var current = this.head;
  while(current!==null && current.data < value){
    prev = current;
    current = current.next;
  }
  prev.next={
    data:value,
    next:current
  };
  if(prev.data === null)
    this.head = prev.next;
};

Whenever we have to insert a node into a sorted single linked list we have to take care of these cases:
1. the node we want to insert is null?
2. the list is empty (==null)?
3. the node to be inserted will fit before the head of the linked list?
4. and ask the interviewer what to do if the linked list contains values == node.value


after checking the 3 things :

Node temp = root;
while(temp.next!= null){
   if(temp.next.value < node.value) temp = temp.next;
   else break;
}
node.next = temp.next;
temp.next = node;

Not the best code ever, but I think it works!

Public void AddtoSortedLinkList(Node head, Node addTo)
{
	if (head == null) {head = addTo; return;}
	if (head.next == null) 
	{
		if (head.item < addTo.item) head.next = addTo;
		else head = addTo;
		return;
	}
	Node prev = new Node();
	Node cur = new Node();
	prev = head;
	cur = prev.next;
	while(cur.next != null)
	{
		if (cur.item < addTo.item)
		{
			prev = cur;
			cur = cur.next;
			continue;
		}else
			break;
	}
	if (cur.item < addTo.Item ) cur.next = addTo;
	else
	{
		addTo.next = cur;
		prev.next = addTo;
	}
}

void InsertToSortedList(stIntList* pSorted, int data)
{
stIntList* pTemp = pSorted;
stIntList* pPrev = NULL;

while(pTemp != NULL)
{
pPrev = pTemp;

if(pTemp->data >= data)
{
stIntList* pNew = new stIntList;
pNew->data = data;
pNew->pNList = pTemp->pNList;
pPrev->pNList = pNew;
std::cout<<"\nInseted Succesfully "<<data<<" at "<<pNew;
break;
}
pTemp = pTemp->pNList;
}
}

void InsertToSortedList(stIntList* pSorted, int data)
{
stIntList* pTemp = pSorted;
stIntList* pPrev = NULL;

while(pTemp != NULL)
{
pPrev = pTemp;

if(pTemp->data >= data)
{
stIntList* pNew = new stIntList;
pNew->data = data;
pNew->pNList = pTemp->pNList;
pPrev->pNList = pNew;
std::cout<<"\nInseted Succesfully "<<data<<" at "<<pNew;
break;
}
pTemp = pTemp->pNList;
}
}

void insert(node **head,int data)
{

if(!head)
return;

struct node *temp=head;
struct node * newnode=(struct node *)(malloc(sizeof(struct node)));
newnode->next=NULL;

while(temp)
{
if(temp->data<data)
{temp=temp->next;
}
else
{
newnode->next=temp->next;
temp->next=newnode;
break;
}

}

}

code in C

Tested for all cases. Worst case complexity will be O(N) if the elements are already sorted before insertion.

// Add in sorted order
	public void addSorted(MyLinkedList<Integer> list, Integer data)
	{
		MyNode<Integer> newNode = new MyNode<Integer>(data);
		
		if(list.head == null)
		{
			list.head = newNode;
			return;
		}
		
		MyNode<Integer> temp = list.head;
		
		while(temp!=null)
		{
			if(temp.data > data)
			{
				MyNode<Integer> temp1 = temp.next;
				temp.next = new MyNode<Integer>(temp.data);
				temp.next.next = temp1;
				temp.data = data;
				break;
			}
			else{
				if(temp.next == null){
					temp.next = newNode;
					break;
				}
				temp = temp.next;
			}
		}

}

temp = head
Node newNode = new Node();
while(temp.key < newNode.value)
{
     temp = temp.next
}

newNode.next = temp.next;
temp.next = newNode;