Inserting in Singly Linked List before the given element

,
1

I am implementing inserttion in singly linked list before given element. Below is my implementation. Please help me.

#include <bits/stdc++.h>
using namespace std;
class Node{
public:
    int data;
    Node* next;
    Node(){
        data=0;
        next= nullptr;
    }
    explicit Node(int input){
        data=input;
        next= nullptr;
    }
};

class implement{
private:
    Node* root;
public:
    implement(){
        root= nullptr;
    }
    void insert(int input){
        root=insert(root, input);
    }
    Node* insert(Node* r, int input){
        if(r== nullptr) r=new Node(input);
        else r->next=insert(r->next, input);
        return r;
    }
    void newNode(int input, int num){
        root=newNode(root, input, num);
    }
    Node* newNode(Node* r, int input,  int num){
        while(r!= nullptr){
            if(r->data==num){
                Node * temp=new Node(input);
                temp->next=r;
                return temp;
            }else if(r->next->data==num){
                Node* temp=new Node(input);
                temp->next=r->next;
                r->next=temp;
                return r;
            } else if(r->next->next->data==num){
                Node * temp= new Node(input);
                temp->next=r->next->next;
                r->next->next=temp;
                return r;
            }
            r=r->next;
        }
        cout << "Element Not found\n";
        return r;
    }
    void print(){
        print(root);
    }
     void print( Node* head){
        while(head!=nullptr) {
            cout<<head->data<<" ";
            head=head->next;
        }
        cout<<endl;
    }
};
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int t=0; cin>>t;
    while(t--){
        auto size=0; cin>>size;
        auto input=0;
        implement obj;
        for(int i=0; i<size; i++){
            cin>>input; // 1 2 3 4 5
            obj.insert(input); 
        }
        // Printing Current List
        obj.print(); // Output 1 2 3 4 5

        // Inserting integer 10 before 1
        obj.newNode(10, 1); 
        obj.print(); // Output 10 1 2 3 4 5

        // Inserting integer 15 before 3
        obj.newNode(15, 3);
        obj.print(); // Output 1 2 15 3 4 5 instead of 10 1 2 15 3 4 5
        obj.newNode(10, 1);
        obj.print();
        obj.newNode(15, 1);
        obj.print();

//        int before = 0;
//        int num; cin>>num;
//        while(num-- ){
//            cin>>input>>before;
//            obj.newNode(input, before);
//        }
        obj.print();
    }
    return 0;

}
2

//SHORT AND CONCISE ITERATIVE SOLUTION …
/head is head of linked list,i is the index, data is data of your node and input will be taken till data!=-1/
// Following is the node structure

#include <iostream>
using namespace std;
class Node {
	public :
	int data;
	Node *next;

	Node(int data) {
		this -> data = data;
		next = NULL;
	}
};




Node* takeInput_Better() {
	int data;
	cin >> data;
	Node *head = NULL;
	Node *tail = NULL;
	while(data != -1) {
		Node *newNode = new Node(data);
		if(head == NULL) {
			head = newNode;
			tail = newNode;
		}
		else {
			tail -> next = newNode;
			tail = tail -> next;
			// OR
			// tail = newNode;
		}

		cin >> data;
	}
	return head;
}


Node* insertNode(Node *head, int i, int data) {
	Node *newNode = new Node(data);
	int count = 0;
	Node *temp = head;

	if(i == 0) {
		newNode -> next = head;
		head = newNode;
		return head;
	}

	while(temp != NULL && count < i - 1) {
		temp = temp -> next;
		count++;
	}
	if(temp != NULL) {
		Node *a = temp -> next;
		temp -> next = newNode;
		newNode -> next = a;
	}
	return head;
}

void print(Node *head) {
	while(head != NULL) {
		cout << head -> data << " ";
		head = head -> next;
	}
}

int main() {

	Node *head = takeInput_Better();
	print(head);
	int i, data;
	cin >> i >> data;
	head = insertNode(head, i, data);
	print(head);


}
1 Like
3

//recursive function just add this for recursive solution and pass the arguments all the things will remain unchanged in my previous code for recusive solution …

Node* insertNodeRec(Node *head, int i, int data) 
{
    if(head==NULL)
    {
     
         return head;
    }   

      if (i==0){
        Node *newnode = new Node(data);
        newnode->next=head;
        head=newnode;
        
        return head;
    }
    
       Node* rrhead=insertNodeRec(head->next, i-1, data); 
    head->next=rrhead;
    
    
    return head;
    
 
}