Facebook Interview Question
Software Engineer InternsCountry: UK
Interview Type: Phone Interview
Assuming the list is singly circular linked list, Hence
Node can be inserted
- at beginning of the list O(1), Swap the data from new node and head and correct the next pointer reference
- In middle of the list - O(n), Traverse to the node
- at the end - O(n) ,
- List is empty and New node will be inserted As first node of the list O(1)
If LIst is doubly circular linked list
Node can be inserted
- at beginning of the list O(1),
- In middle of the list - O(n), Traverse to the node,
- at the end - O(1) , Check if new node has greater value then last node , then insert it at beginning and make second node as head, and new node as last pointer
- List is empty and New node will be inserted As first node of the list O(1)
Feel free to correct me.....
Node* sortedInsert(Node* head , int val)
{
Node* prev = NULL;
Node* origHead = head;
Node* ins = new Node(val);
if(!head){ // if it is empty
head = ins;
ins->next = head;
return origHead;
}
while(head->next != origHead && head->data < val){
prev = head;
head = head->next;
}
if(prev){
prev->next = ins;
ins->next = head;
}else{
ins->data = head->data;
head->data = val;
ins->next = head->next;
head->next = ins;
}
return origHead;
}
static class Node{
int data;
Node next;
Node(int d){
data = d;
}
}
public static Node insert(Node n, int d){
if(n == null)
return new Node(d);
Node p = n;
if(p.data > d ){
while(p.data < p.next.data){
p = p.next;
}
Node l = p.next;
Node t = new Node(d);
p.next = t;
t.next = l;
p = p.next;
return p;
}else{
Node c = p;
while(p.data < p.next.data && p.data < d){
c = p;
p = p.next;
}
if(d < p.data){
Node t = new Node(d);
c.next = t;
t.next = p;
}else{
Node t = new Node(d);
Node l = p.next;
p.next = t;
t.next = l;
}
return n;
}
}
Node *Insert(Node *head, int val)
{
Node *n = new Node(val);
if (!head) {
n->next_ = n;
head = n;
} else {
n->next_ = head->next_;
head->next_ = n;
swap(n->val_, head->val_);
}
for (n = head; n->next_ != head && n->val_ > n->next_->val_; n = n->next_) {
swap(n->val_, n->next_->val_);
}
return head;
}
Assuming the list is singly circular linked list.
1- List is empty: a New node will be the head node
2- List is not empty: the location will be found and a new node will be inserted in O(n)
- RF May 10, 2017