struct Node
{
	int data;
	Node * next;
	Node(int _data, Node* _next=nullptr) :  data(_data), next(_next) {}
};

void insertNode(Node * nodeToBeInserted, Node* previousNode)
{
	Node * tmp = previousNode->next;
	previousNode->next = nodeToBeInserted;
	nodeToBeInserted->next = tmp;
}

void expand(Node * begin)
{
	Node * itr = begin;
	if(itr == nullptr)
		return;
	else
	{
		while(itr->next)
		{
			if(itr->data == itr->next->data)
			{
				int k = itr->data;

				for (int i = 0; i < k; i++)
				{
					insertNode(new Node(k), itr);
					itr = itr->next;
				}

				itr = itr->next;
			}
			else
			{
				itr = itr->next;
			}
		}
	}
}

int main()
{
	Node * beg = new Node(0);
	beg->next = new Node(0);
	beg->next->next = new Node(1);
	beg->next->next->next = new Node(1);
	beg->next->next->next->next = new Node(2);
	beg->next->next->next->next->next = new Node(2);
	beg->next->next->next->next->next->next = new Node(2);
	beg->next->next->next->next->next->next->next = new Node(3);

	expand(beg);

	return 0;
}