Google Interview Question Software Engineer / Developers
Country: United States
The case 2 can be optimized as follows. Instead of traversing the list to find the previous node we can insert the new node after head and then replace the value of new node and head.
the code for case 2 in this approach is
// Case 2 of the above algo
else if (current->data >= new_node->data)
{
/* Insert the new node after head and then swap the values of head node and the new node. Note that current is pointing to head. As the header node pointer is still the same there is no need to modify it.*/
new_node->next = current->next;
current->next = new_node;
int temp = new_node->data;
new_node->data=current->data;
current->data=temp;
}
bool flag = true;
list *node = HEAD;
if(HEAD==NULL)
{
HEAD = myNode;
myNode->next = HEAD;
}
else{
while(flag)
{
if(node->key < myNode->key)
{
if(node->next->key >= myNode->key || node->next == HEAD)
{
list *temp;
temp = node->next;
node->next = myNode;
myNode->next = temp;
flag = false;
}
else
node = node->next;
}
}
}
inster(head,v)
{
temp=head;
create a new node of value v and let it be newNode;
while(temp!=head && teamp.value<=head)
{
temp=temp.next;
}
newNode.next=temp.next;
temp.next=new.node;
}
Worst case complexity o(n);
This may not work.
You are initializing temp to head, and right away, checking whether temp != head, which is always false and the loop will never get executed.
temp = head // initialize
while (temp != head) // always false
void ins(node *t,int num,int d=99999)
{
int diff=num - temp->next->value;
if (dif < d && diff > 0)
ins(t->next,num,diff);
else
{
node *temp=t->next;
t->next=new node(num);
t->next->next=temp;
}
}
This will not work if the input numbers are negative. This can be solved without the third argument as well.
@abhishek It will even if the nos. are negative, try it. Give a case where it's not working?
void insert(Node *head, Node *node)
{
if(head == NULL)
{
head = node;
head->next = head;
return;
}
Node *preNode = head;
Node *curNode = head;
while(curNode->data < node->data)
{
preNode = curNode;
curNode = curNode->next;
if(curNode == head || curNode->data < preNode->data)
break;
}
node->next = curNode;
preNode->next = node;
}
Use two pointers.Select any node as head node and let the head pointer(h) point it.Use another pointer to traverse the list let it be t.
let value x needs to be inserted.
1.Check if h.value is less than X.If yes then insert x just before head.
2.else traverse linked list unless t.next.value>x or t.next==h.Insert x after t.
public static void insert(Node head,Node newNode)
{
if(head==null)return;
else if(head.next==null || head.next==head)
{
head.next=newNode;
newNode.next=head;
return;
}
final Node[] pair={head,head.next};
do
{
if(pair[0].value <= newNode.value && newNode.value<= pair[1].value)
{
pair[0].next=newNode;
newNode.next=pair[1];
return;
}
else
{
pair[0]=pair[0].next;
pair[1]=pair[1].next;
}
}while(pair[0]!=head);
}
The idea is to find the two nodes between which the new value lies, while taking care of the end conditions.
if (headNode == null || length == 0) {
// If the length of the list is 0, newNode is the list.
headNode = newNode
newNode.next = newNode
newNode.prev = newNode
} else if (length == 1) {
// The length is 1, the headNode and newNode are linked to each other.
headNode.next = newNode
headNode.prev = newNode
newNode.next = headNode
newNode.prev = headNode
} else {
// If length is more than 1, find the nodes whose values surround newNode's value. Keep a counter to check the case when all the values in the list are the same and keeping the loop to go into an infinite loop.
loopNode = headNode
counter = 0
while (counter < length) {
if (newNode.value >= loopNode.value && newNode.value <= loopNode.next.value) {
break
} else {
counter++
loopNode = loopNode.next
}
}
newNode.prev = loopNode
newNode.next = loopNode.next
newNode.prev.next = newNode
newNode.next.prev = newNode
}
void insertValue(Node head, Node tail, int value){
if(head == null){
Node t = new Node(value);
head = t;
t.next = head;
tail =t;
}
if(value<head.value){
Node t = new Node(value);
t.next = head;
head =t;
tail.next =t;
}
Node pre = head;
while(pre.next!=tail){
if(pre.value>value){
Node t = new Node(value);
t.next = pre.next;
pre.next = t;
break;
}else{
pre= pre.next;
}
}
if(pre == tail){
Node t = new Node(value);
t.next = pre.next;
pre.next = t;
tail = t;
}
}
void insertValue(Node* head, Node* newNode)
{
int val = newNode->data;
if (head->next != head)
// list has more than one node
{
while (true)
{
if ( (head->data <= val && head->next->data >= val)
|| (head->data <= val && head->data >= head->next->data) )// check for the node whose next is head again
break;
else
{
head = head->next;
}
}
}
newNode->next = head->next;
head->next = newNode;
}
The basic code is to check whether the inserted node value lies between the current node and the next node. If so, insert the node and set the next pointers accordingly.
Two special cases need to be handled:
1. The list has a single node. In this case, we just set the next of the single node an the new node to each other.
2. The node to be inserted has a value between the head and the node preceding it. For this, I have the following check:
head->data <= val && head->data >= head->next->data;
public ListNode insert(ListNode head, ListNode newNode)
{
if(head == null)
{
head = newNode;
head.next = head;
return head;
}
ListNode pre = head;
ListNode cur = head.next;
while(cur != head)
{
if(newNode.val <= cur.val && newNode.val >= pre.val)
{
pre.next = newNode;
newNode.next = cur;
return head;
}
pre = cur;
cur = cur.next;
}
pre.next = newNode;
newNode.next = cur;
if(preNode.val < cur)
return preNode;
else
return cur;
}
please clarify one thing to me....
do we need to only insert in an already sorted linked list or do we need to sort the linklist as we insert.
Void Insert(Node N)
{
if (head == null) // linked list is empty
{
head = N; tail = N; tail.Next = head;
}
else
{
Node temp = tail.Next; // since this is circular tail will point to head
Tail.Next = N;
N.Next = temp; // correct
tail = N;
}
}
yup Mr. Anonymous....
cant u sort that link list...
if u can ... use my code to insert a value in it...
else
tell me i will give u code for sorting too...
@Anonymous you are right. I think we need to traverse from head comparing the next value with the given node. If the value of next node is greater insert the node before that node. As the list is sorted you will defintely find a place for this node in O(n).
no Mr. i m not gonna sort at each insertion.... firstly i will sort that link list and then i m gonna insert into it...
Void Insert(Node N)
{
if (head == null) // linked list is empty
{
head = N; tail = N; tail.Next = head;
}
else
{
Node temp=head;
while(N<=temp)
{
temp = head.Next; // since this is circular tail will point to head
}
head.Next = N;
N.Next = temp; // correct
}
}
Jayram your code has lot of problem
1.temp = head.Next; insteam you should write temp = temp.next
2.while(N<=temp) instead while(N.value<=temp.value)
3. If N.value is > all the values in the list, it will invoke infinite loop
4.head.Next = N; I dont know wht are you doing here by inserting on head. you should rather insert it jst before temp by having another variable temp1 = temp b4 doing temp=temp.next; so temp1.next = N nd N.next=temp would hv done the trick
some part would have been
Node temp1 = head;
while(N.value<=temp.value)
{
temp1 = temp;
temp = head.Next; // since this is circular tail will point to head
}
temp1.Next = N;
N.Next = temp; // correct
jayram i was going through ur code, expecting it would be some real good solution for the problem. But man what is that??your code is a shit and you are talking like you are a pro.Plz do not post a sol. until u make sure that its a little bit tricky & "not so obvious"algo u are using.
- Anonymous September 14, 2012/* structure for a node */ struct node { int data; struct node *next; }; /* function to insert a new_node in a list in sorted way. Note that this function expects a pointer to head node as this can modify the head of the input linked list */ void sortedInsert(struct node** head_ref, struct node* new_node) { struct node* current = *head_ref; // Case 1 of the above algo if (current == NULL) { new_node->next = new_node; *head_ref = new_node; } // Case 2 of the above algo else if (current->data >= new_node->data) { /* If value is smaller than head's value then we need to change next of last node */ while(current->next != *head_ref) current = current->next; current->next = new_node; new_node->next = *head_ref; *head_ref = new_node; } // Case 3 of the above algo else { /* Locate the node before the point of insertion */ while (current->next!= *head_ref && current->next->data < new_node->data) current = current->next; new_node->next = current->next; current->next = new_node; } } /* Function to print nodes in a given linked list */ void printList(struct node *start) { struct node *temp; if(start != NULL) { temp = start; printf("\n"); do { printf("%d ", temp->data); temp = temp->next; } while(temp != start); } } /* Driver program to test above functions */ int main() { int arr[] = {12, 56, 2, 11, 1, 90}; int list_size, i; /* start with empty linked list */ struct node *start = NULL; struct node *temp; /* Create linked list from the array arr[]. Created linked list will be 1->2->11->56->12 */ for(i = 0; i< 6; i++) { temp = (struct node *)malloc(sizeof(struct node)); temp->data = arr[i]; sortedInsert(&start, temp); } printList(start); getchar(); return 0; }