Amazon Interview Question
Testing / Quality AssurancesAn approach for this problem would be each time check whether the data is even or odd, if it is even, link it with the tail node [keep 2 pointers, one pointing towards the head and the other always pointing towards the tail], thus all the even numbers would be towards the tail and we would have the odd numbers followed by the even numbers....
split the link list into two lists, one for even numbers, one for odd numbers. This should be doable by going through the original list. The head/tail pointers of these two lists are maintained. So, 4 more additional pointers.
When all nodes are handled, attach the even number list to the end of the odd number list.
split the link list into two lists, one for even numbers, one for odd numbers. This should be doable by going through the original list. The head/tail pointers of these two lists are maintained. So, 4 more additional pointers.
When all nodes are handled, attach the even number list to the end of the odd number list.
Nishit's solution has the issue that we might visit the numbers once again since they have been attached to the tail node. In order to prevent this we can have another pointer that maintains the reference to the tail node in the first run. Once the pointer used for traversal reaches the new pointer we stop because there is no need to traverse further.
The problem is not that hard.
We need to traverse through the complete list with dividing it into the two list each having the head as the first odd and even element. Only the node-> next field needs to be changed to point to the next alternate node.
Test cases have to be checked for 0,1,odd and even number of nodes.
here it is i had not tested much but it seems to be correct
Arrange(List** Head)
{
List* Node=*Head;
// we want all even at the start
while(Node)
{
int Flag;
if(Node->data%2==0)
{
Node=Node->Next; // move to the next element
continue; // skip entire while then
}
// we will come till this line if the number is not even
List *temp=Node->next;
List* NextStart=Node->next;
while(temp)
{
int Flag=0;
if (temp%2==0)
{
int MyTemp=temp->data;
temp->data=Node->data;
Node->data=MyTemp;
Flag=1;
}
temp=temp->next;
} // end of while
if (!Flag) // If we reached the end of the link list then insert node at the end of link list
{
*Head=Node->next;
temp=*Head;
while(temp)
{
temp=temp->next;
}
Node->next=NULL;
temp->Next=Node;
}
Node=NextStart;
}// end of while
}
Arrange(List** Head)
{
List* Node=*Head;
// we want all even at the start
while(Node)
{
int Flag;
if(Node->data%2==0)
{
Node=Node->Next; // move to the next element
continue; // skip entire while then
}
// we will come till this line if the number is not even
List *temp=Node->next;
List* NextStart=Node->next;
while(temp)
{
int Flag=0;
if (temp%2==0)
{
int MyTemp=temp->data;
temp->data=Node->data;
Node->data=MyTemp;
Flag=1;
}
} // end of while
if (!Flag) // If we reached the end of the link list then insert node at the end of link list
{
*Head=Node->next;
temp=*Head;
while(temp)
{
temp=temp->next;
}
Node->next=NULL;
temp->Next=Node;
}
Node=NextStart;
}// end of while
}
First find out the total no of element in the list. -- O(n) complexity.
Then take 2 pointer such that 1 pointing to the start and other pointing to the middle.[again O(n/2) complexity]
Now check if the no is odd move it in the first half otherwise move it in the second half --- complexity O(nlogn)
therefore the total complexity is O(nlogn)
previousNode := null
node: = list.firstNode
while node != null
{
If(node.value % 2 == 0)
{
Node1 := node.next
While(node1 != null)
{
If(node1.value % 2 != 0)
{
Found = true;
If(previousNode == null)
{
List.firstNode := node.next
previousNode := node.next
Node.next := node1.next
Node1.next := node
Break;
}
Else{
previousNode.next = node.next
node.next = node1.next
node1.next = node
` break
}
}
Node1 := node1.next
}
if(!found)
{
Break;
}
}
If (!found)
{
If(null == previousNode)
{
previousNode := node;
node:= node.next
}
Else
{
Node:= previousNode.next.next
previousNode := previousNode.next
}
}
Found = false
}
take a pointer(ptr1) pointing to the header.. move it until the value of the node is odd and stop if you find and even number. now from here take another pointer(ptr2).. and keep moving it, until you find an odd number, swap there values not the node.
I think this way we can put all odd numbers before the even numbers. Correct if I am wrong.
I am thinking along the same lines of kk. The question says to not create any additional list, just work with the list that's given.
It's been a while since I coded, so in pseudo-code:
take evenPtr and find the FIRST even numbered node.
take oddPtr and find the FIRST odd numbered node occurring after an even numbered node.
swap the values pointed to by evenPtr and oddPtr.
advance evenPtr by 1. evenPtr now points to the FIRST even number in the list, which will be replaced by the next odd number (if we find one).
move oddPtr until we reach the next odd node. repeat swap process above.
This approach seems to be a better one. O(N) time complexity. Code snippet following approach would be -
SNode *pList = pRoot;
SNode *pEvenNode = NULL;
// Make the Check node, point to the first even element of the list
while(pList != NULL)
{
if(pList->nData %2 == 0)
{
pEvenNode = pList;
pList = pEvenNode->pNext;
break;
}
pList = pList->pNext;
}
// If there was no even element in the list
if(!pEvenNode)
return;
while(pList != NULL)
{
if(pList->nData % 2 != 0)
{
int nData = pList->nData;
pList->nData = pEvenNode->nData;
pEvenNode->nData = nData;
pEvenNode = pEvenNode->pNext;
}
pList = pList->pNext;
}
Here is my solution ..I have tested it works fine ..
I am doing this in O(n) time and it requires some temp pointer ...so space complexity is much less ..
I think time complexity can be improved to O(n/2)
Node* evenodd(Node *head)
{
Node *odd,*even,*temp1,*temp2,*head1,*head2;
odd = head;
even = head->next;
head1 = even;
head2 = odd;
while(odd != NULL && even != NULL)
{
temp1 = odd->next->next;
if(even->next == NULL)
temp2 = NULL;
else
temp2 = even->next->next;
odd->next = temp1;
even->next = temp2;
odd = temp1;
even = temp2;
}
temp1 = head1;
while(temp1->next != NULL)
temp1 = temp1->next;
temp1->next = head2;
return head1;
}
Element *OddEven(Element **head)
{
Element *cur = *head;
Element *pre = null;
Element *insertAfter = null;
Element *newHead = *head;
while(cur != null)
{
if(cur->data%2 != 0)
{
if(insertAfter != null)
{
Element *tempCurNext = cur->next;
Element *tempInsertNext = insertAfter->next;
insertAfter->next = cur;
cur->next = tempInsertNext;
cur = tempCurNext;
insertAfter = insertAfter->next;
}
else if(pre == insertAfter)
{
insertAfter = cur;
pre = cur;
cur = cur->next;
}
else
{
Element *tempCurNext = cur->next;
pre->next = *tempCurNext;
cur->next = newHead;
newHead = cur;
cur = tempCurNext;
insertAfter = newHead;
}
}
else
{
pre = cur;
cur = cur->next;
}
}
return *head;
}
Here I = insertAfter
c = current
p = previous
h = head
Starting with Odd.
I p c
null null 1->2->4->5->7->null
I C
1->2->4->5->7->null
P
I C
1->2->4->5->7->null
P
I C
1->2->4->5->7->null
P
I C
1->5->2->4->7->null
P
I C
1->5->7->2->4->null
P
Starting with event.
I p c
null null 2->4->5->7->null
I p c
null 2->4->5->7->null
I p c
null 2->4->5->7->null
I p c
5->2->4->7->null
H
I p c
5->7->2->4->null
H
Traverse the linked list.
If you find a odd number insert that number in front of the linked list and continue.
At the end of the iteration all the odds will appear before even.
void reorderLinkedList(NODE first)
{
NODE temp;
if( first == NULL && first->next == NULL)
return ;
NODE cur,prev,temp;
cur = first->next;
prev = first;
while( cur != NULL)
{
if( cur->data%2 != 0 )
{
//insert the odd number in front.
temp = prev->next = cur->next;
cur->next = first;
first = cur;
cur = temp;
}
else
{
prev = cur;
cur = cur->next;
}
}
}
C code:
Logic is simple. If the first element is even, then search for the first odd element (this is important). Then, adjust even and odd pointers so that they are one step behind the curr element being checked. Then check the value of curr->val % 2. If its zero, then add it to even list otherwise add to odd list. The main thing to observe is that at any given point in time, even and odd pointers should be one step behind the curr pointer. I ended up using a lot of temp variables, hope somebody can provide good suggestions.
NODE_PTR ArrangeEvenOdd(NODE_PTR head)
{
if(head == NULL) {
return NULL;
}
int flag = 0;
NODE_PTR odd = head;
NODE_PTR even = head;
NODE_PTR prev = NULL;
int val = head->val;
if(val % 2 == 0) {
flag = ODD;
while(odd != NULL && odd->val % 2 == 0) {
prev = odd;
odd = odd->next;
}
}
else {
flag = EVEN;
while(even != NULL && even->val % 2 != 0) {
prev = even;
even = even->next;
}
}
if(even == NULL || odd == NULL) {
return head;
}
NODE_PTR even_head = even;
NODE_PTR odd_head = odd;
NODE_PTR curr = NULL;
if(flag == EVEN) {
head = odd;
odd = prev;
odd->next = even->next;
curr = even->next;
}
else {
head = even;
even = prev;
even->next = odd->next;
curr = odd->next;
}
while(curr != NULL) {
val = curr->val;
if(val % 2 == 0) {
odd->next = curr->next;
curr = curr->next;
even = even->next;
flag = EVEN;
}
else {
even->next = curr->next;
curr = curr->next;
odd = odd->next;
flag = ODD;
}
}
even->next = odd_head;
return even_head;
}
* Indentation may be bad *
what if:
The head node, which may be odd-valued or even-valued, should remain unchanged.
For the general case where the given list has both odd-valued nodes and even-valued nodes, the processed list would take the form of
odd1 -> even1 -> odd2 -> even2 -> ... if the head node is odd-valued, or
even1-> odd1-> even2-> odd2 -> ...if the head node is even-valued.
The order in which the odd-valued nodes appear in the given list should be preserved when the list is processed, AND similarly for the order of the even-valued nodes.
Any nodes (may be odd-valued or even-valued) in the given list that cannot be interleaved (because there are no more "partners" left) should appear as the tail portion of the processed list AND in the same order as they appear in the given list.
I think this is similar kind of problem in which there is a link list having only 0 and 1. You have to arrange the no such that all 0 come before 1.
void RearrangeListStable(listptr *head)
{
listptr cur, prev, evenList, firstEven, lastEven;
int i, len;
i=0; len = findLength(*head);
if(len <= 1) // nothing to rearrange
return;
evenList = firstEven = lastEven = prev = NULL;
cur = *head;
while(i<len && cur)
{
if (cur->data %2 == 0) // if even
{
firstEven = lastEven = cur;
while(lastEven->link && lastEven->link->data %2 == 0)
{
lastEven = lastEven->link;
i++;
}
if (lastEven->link == NULL && prev == NULL) //the entire list contains even
break;
else if(prev)
{
prev->link = lastEven->link;
cur = prev;
}
else if (!prev)
*head = cur = lastEven->link;
lastEven->link = NULL;
if(!evenList)
evenList = firstEven;
else
appendList(&evenList, firstEven);
}
prev = cur;
cur = cur->link;
i++;
}
appendList(head, evenList);
displayList(*head);
}
we can do bubble sort with arranging elements only when they are even
- cunomad September 15, 2009