Let P he a linked list. Write a 'C' function called split to create two linked lists Q and R. Q should contain
all elements in odd positions of P and R contains the remaining elements. Your function should not change list
P. What is the eomplexity of your program ? 5

The program provided below is about linked list whose nodes are created using a structure and several function are created to create a linked list, and the function required to divide the linked list into two is created using the divide function. Function that creates a node to be inserted in the linked list is created by the function newNode which is implemented as follows:

// function to create a node
struct Node* newNode(int data) {
   Node* node=new Node;
  node->data=data;
  node->next=NULL;
   return node;
}

Step-by-step explanation

Function divide() takes address of root node of the linked list to be divided into two and is implemented using a while loop to add odd position elements in one lined list and remaining elements in abother linked list and is implemented as follows:

// required function
void divide(Node* root){
    Node *root1=NULL;
    Node *root2=NULL;
    int i=1;
   while(root!=NULL){
       if(i%2!=0){
           insertNewNode(&root1, root->data);
        }else{
           insertNewNode(&root2, root->data);
        }
        i++;
       root=root->next;
    }
   cout<<"Printing list with odd position contents: ";
   printLinkedList(root1);
   cout<<"Printing list with even position contents: ";
   printLinkedList(root2);
}

Program Code:

#include 
using namespace std;

// node of a linked list
struct Node{
   int data;
   Node* next;
};

// function to create a node
struct Node* newNode(int data) {
   Node* node=new Node;
  node->data=data;
  node->next=NULL;
   return node;
}

// function to insert the node created using function newNode in the linked list
void insertNewNode(Node** root, int data){
   Node* node=newNode(data);
   Node* ptr;
  if(*root==NULL){
     *root=node;
   }
   else{
      ptr=*root;
     while(ptr->next != NULL) {
        ptr=ptr->next;
      }
     ptr->next=node;
   }
}

// prints contents of the linked list
void printLinkedList(Node* root){
   while(root != NULL){
     cout<data<<" -> ";
     root=root->next;
   }
   cout<<"NULL"<data);
        }else{
            insertNewNode(&root2, root->data);
        }
        i++;
       root=root->next;
    }
   cout<<"Printing list with odd position contents: ";
   printLinkedList(root1);
   cout<<"Printing list with even position contents: ";
   printLinkedList(root2);
}

// creating orginal linked list
Node* createLinkedList(int arr[], int n){
   Node *root = NULL;
   for(int i=0;i

Program Code

#include <iostream> using namespace std; / / node of a linked list struct Nodef int data; Node* next; / / function to create a node struct Node* newNode (int data) { Node* node=new Node; node->data=data; node->next=NULL; return node; / / function to insert the node created using function newNode in the linked list void insertNewNode (Node** root, int data) { Node* node=newNode (data) ; Node* ptr; if (*root==NULL) { *root=node; else{ ptr=*root; while(ptr->next != NULL) { ptr=ptr->next; ptr->next=node;

/ / prints contents of the linked list void printLinkedList (Node* root) { while (root ! = NULL) { cout< <root->data< <" -> "; root=root->next; cout< <"NULL"< <endl; // required function void divide (Node* root) { Node *root1=NULL; Node *root2=NULL; int i=1; while ( root ! =NULL) { if(1%2!=0) { insertNewNode (&root1, root->data) ; }else{ insertNewNode (&root2, root->data) ; i++; root=root->next; cout<<"Printing list with odd position contents: printLinkedList (root1); cout<<"Printing list with even position contents: printLinkedList ( root2) ;

// creating orginal linked list Node* createLinkedList(int arr, int n) { Node *root = NULL; for (int i=0;
i 2, 3, 4,5}, n=5; Node* root=createLinkedList(arr , n) ; printLinkedList (root) ; divide ( root ) ; return 0;

Output

1 -> 2 -> 3 -> 4 -> 5 -> NULL Printing list with odd position contents: 1 -> 3 -> 5
-> NULL Printing list with even position contents: 2 -> 4 -> NULL