CareerCup

we can do bubble sort with arranging elements only when they are even

An 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....

try to keep any odd position fixed for odds and even for even....like when u find any odd/even at even/odd index swap it with next even/odd at odd/even index......don't know the complexity but I think this will do...

comments are welcome...thanks...

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.

Is this a single linked list or double linked list? If it is a double linked list, start from both ends and keep swapping.

If it is a single linked list, we need at least some storage to improve time complexity.

No valid answer so far! Agreed with Erik though.

If it is a single linked list, we can do it as majun8cn said. Keep linking odd and even nodes and finally join both of these lists.

i misunderstood the problem as in we need to reform the linked list such that odd numbers occur prior to even alternatively something like odd-even-odd-even----...which I've already faced in an interview long back....this one looks different......

for this 1 ...majun's solution seems fine...

Alternate thought... [This would work better for 'arrays' though]
scan an element. if even, swap with the next element... and keep swapping till the element moves to the end.
decrement 'end' by 1.
repeat for all elements.

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


}

cunomad can you please explain your code. just 2/3 lines explanation would be good enough to make sense.

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.

yup this is the rght one

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

ohh fish minor correction ..I did it such that even number come before odd ..but question is asking just opposite which is simple ..so only 2 lines need to be changed ..

temp1 = head2;

temp1->next = head1;

return head2;

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.

it makes studying efficient

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