Microsoft Interview Question Software Engineer in Tests
This solution wont work if the element to be inserted is the first element i.e if we have 2 3 4 5 and we try to insert 1.
Same goes with the last element also.
You need to check these conditions too.
Need to check these cases:
Case 1. An inserted node is the first one to be added to an empty list.
Case 2. The inserted node’s key is less than those of all others in the list; thus, the node goes at the beginning of a nonempty list.
Case 3. The key is greater than all the others; thus, the node goes at the end of the list.
Case 4. The key lies between two others; thus, the node goes in the middle of the list somewhere.
you are probably asked to write the O(n*log) solution, this is O(n).
A simple solution would be using merge sort...
Scan through the list and count n. Then you divide by considering first n/2 and last n/2. Then "break" the list into parts, sort them recursively and "join" the two lists.
void insert(Node **header, int value)
{
if(**header && *header)
{
if((*header)->value>value)
{
Node *newHeader=new Node();
newHeader->value=value;
newHeader->next=*header;
*header=newHeader;
}
else
{
Node *current=*header;
while(current->next && current->next<=value)
{
current=current->next;
}
Node *newNode = new Node();
newNode->value = value;
newNode ->next = current->next;
current->next =newNode;
}
}
else if(**header && *header == NULL)
{
*header=new Node();
*header->value=value;
}
}
while(node->next)
- Anonymous April 01, 2010{
if(node->data<=val && node->next->data >=val)
{
new->next=node->next;
node->next=new;
}
else
{
node=node->next;
}
}