1.

How will you modify a linked list of integers so that all even numbers appear before all odd numbers in the modified linked list? Also, keep the even and odd numbers in the same order.

Answer»

Example:
Input: 17->15->8->12->10->5->4->1->7->6->NULL
Output: 8->12->10->4->6->17->15->5->1->7->NULL

Algorithm:
The approach is to divide the linked list into two sections, one with all even nodes and the other with all odd nodes. In order to split the Linked List, traverse the original Linked List and move all odd nodes to a new Linked List. The original list will include all the even nodes at the end of the loop, while the odd node list will have all the odd nodes. We must place all the odd nodes at the end of the odd node list to maintain the same ordering of all nodes. And, in order to do it in real-time, we'll need to maintain track of the last pointer in the odd node list. Finally, the odd node linked list is to be ATTACHED after the even node linked list.

Implementation:

Node* separateEvenOdd(struct Node *head){ // Starting node of the list having // even VALUES Node *evenStart = NULL; // Starting node of the list having odd values Node *oddStart = NULL; // Ending node of the list having even values Node *evenEnd = NULL; // Ending node of the list having odd values Node *oddEnd = NULL; // Node for list traversal. Node *currentNode; for(currentNode = head; currentNode != NULL; currentNode = currentNode -> next) { int value = currentNode -> value; // If the current value is even, add // it to the list of even values. if(value % 2 != 0) { if(oddStart != NULL) { oddEnd -> next = currentNode; oddEnd = oddEnd -> next; } else { oddStart = currentNode; oddEnd = oddStart; } } // If current value is odd, add // it to the list of odd values. else { if(evenStart != NULL) { evenEnd -> next = currentNode; evenEnd = evenEnd -> next; } else { evenStart = currentNode; evenEnd = evenStart; } } } // If any of the two- odd list or even list is empty, // no change is required if(!oddStart || !evenStart) { return; } // Add the odd list after the even list. evenEnd -> next = oddStart; oddEnd -> next = NULL; // Modify the head pointer to // the start of the even list. head = evenStart; return head;}

Time Complexity: O(n)
SPACE Complexity: O(1)


Discussion

No Comment Found

Related InterviewSolutions