Answer to Question #311211 in C++ for Shah jee

Question

Let P be a linked list.Write a C++ function callef split to create two linked lists Q and R.Q should contain all elements in odd position of P and R contains remaining elements.Your Function should not change list p.What is the conplexity of your program.

Answer 1

#include <iostream>
using namespace std;


struct Node {
    int value;
    Node* next;
    Node(int v, Node* n=nullptr) {
        value = v;
        next = n;
    }
};


Node* create_list(int a[], int n) {
    Node* head = new Node(a[0]);


    for (int i=1; i<n; i++) {
        head = new Node(a[i], head);
    }
    return head;
}


void print_list(Node* head) {
    cout << head->value;


    head = head->next;
    while (head) {
        cout << " -> " << head->value;
        head = head->next;
    }
    cout << endl;
}


void split(Node* p, Node*& r, Node*& q) {
    int i;
    Node* last_r;
    Node* last_q;


    r = nullptr;
    q = nullptr;
    if (!p) {
        return;
    }
    r = new Node(p->value);
    last_r = r;
    p = p->next;
    if (!p) {
        return;
    }
    q = new Node(p->value);
    last_q = q;


    i = 2;


    while (p->next) {
        p = p->next;
        i++;
        if (i%2 == 1) {
            last_r->next = new Node(p->value);
            last_r = last_r->next;
        }
        else {
            last_q->next = new Node(p->value);
            last_q = last_q->next;
        }
    }
        
}


int main() {
    const int N=10;
    int a[N];


    for (int i=0; i<N; i++) {
        a[i] = 10-i;
    }
    Node* p = create_list(a, N);
    cout << "P: ";
    print_list(p);


    Node* r;
    Node* q;
    split(p, r, q);
    cout <<"R: ";
    print_list(r);
    cout << "Q: ";
    print_list(q);


    return 0;
}