## Microsoft Interview Question

**Team:**Office

**Country:**United States

**Interview Type:**In-Person

```
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;
}
```

I think you are missing the case when the node you want to insert is lower than the head

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;
```

you are missing some special cases, what if you have to insert at the head or at the end, and you don't update head pointer

- Anonymous January 25, 2013