Answer to Question #334669 in C++ for sss

Question

Given a linked list containing n nodes. The problem is to insert a new node

with data x at the middle of the list. If n is even, then insert the new node

after the (n/2)th node, else insert the new node after the (n+1)/2th node

Answer 1

#include <iostream>

using namespace std;

struct Node
{
	int data;
	struct Node *next;
	Node(int _data) :data(_data), next(NULL) {}
	Node(){}
};


class LinkedList
{
	// Head pointer
	Node* head;


public:
	// default constructor. Initializing head pointer
	LinkedList()
	{
		head = NULL;
	}


	// inserting elements (At start of the list)
	void insert(int val)
	{
		// make a new node
		Node* new_node = new Node;
		new_node->data = val;
		new_node->next = NULL;


		// If list is empty, make the new node, the head
		if (head == NULL)
			head = new_node;
		// else, make the new_node the head and its next, the previous
		// head
		else
		{
			new_node->next = head;
			head = new_node;
		}
	}
	// inserting elements (At middle of the list)
	void insertMiddle(int val)
	{
		// make a new node
		Node* new_node = new Node;
		new_node->data = val;
		new_node->next = NULL;


		// If list is empty, make the new node, the head
		if (head == NULL)
			head = new_node;
		// else, make the new_node the head and its next, the previous
		// head
		else
		{
			int nodes = countNodes();
			int n = 1;
			Node* temp = head;
			if (nodes % 2 == 0)
			{
				while (n!=nodes/2)
				{
					temp = temp->next;
					n++;
				}
			}
			else
			{
				while (n != (nodes + 1) / 2)
				{
					temp = temp->next;
					n++;
				}
			}
			new_node->next = temp->next;
			temp->next=new_node;
		}
	}
	int countNodes()
	{
		int n = 0;
		Node* temp = head;
		while (temp != NULL)
		{
			temp = temp->next;
			n++;
		}
		return n;
	}
	void display()
	{
		Node* temp = head;
		while (temp != NULL)
		{
			cout << temp->data << " ";
			temp = temp->next;
		}
		cout << endl;
	}
};


int main()
{
	LinkedList l;
	l.insert(6);
	l.insert(9);
	l.insert(1);
	l.insert(3);
	l.insert(7);
	l.insertMiddle(23);
	l.display();
	l.insertMiddle(33);
	l.display();
}