Here is an example C++ program that implements the algorithm for separating even position nodes from odd position nodes in a singly linked list:
#include <iostream>
using namespace std; // Node structure for a singly linked list struct Node { int data;
Node* next; }; // Function to create a new node with the given data Node* newNode(int data) { Node* temp = new Node; temp->data = data; temp->next = NULL; return temp; }
// Function to separate even and odd position nodes void separateEvenOdd(Node* head) { // Initialize dummy nodes for even and odd lists Node* evenHead = newNode(0); Node* oddHead = newNode(0); Node* even = evenHead; Node* odd = oddHead; int position = 1; // Start at position 1 (odd)
// Iterate through the original list
while (head) { if (position % 2 == 0) { // Add node to even list even->next = head; even = even->next; } else { // Add node to odd list odd->next = head; odd = odd->next; } head = head->next; position++; } // End the lists
even->next = NULL; odd->next = NULL; // Print the even list cout << "Even Position Nodes:" << endl; even = evenHead->next; while (even) { cout << even->data << " "; even = even->next; } cout << endl; // Print the odd list
cout << "Odd Position Nodes:" << endl; odd = oddHead->next; while (odd) {
cout << odd->data << " "; odd = odd->next; }
cout << endl;} int main() { // Create a test linked list Node* head = newNode(1); head->next = newNode(2); head->next->next = newNode(3); head->next->next->next = newNode(4); head->next->next->next->next = newNode(5); // Separate even and odd position nodes separateEvenOdd(head); return 0; }
In this program, we have defined a Node structure for a singly linked list and a newNode function for creating new nodes with the given data. We also have a separateEvenOdd function that takes the head of the original list as an argument.
The separateEvenOdd function starts by initializing two dummy nodes for the even and odd lists, and two pointers – even and odd – that will be used to add nodes to these lists. It also initializes a counter, position, which starts at 1 (odd).
The function then iterates through the original list using a while loop. For each node, it checks the value of position modulo 2. If the result is 0, it adds the current node to the even list by updating the even pointer. If
