#include <iostream>
using namespace std;
class LinkedList;
class node{
int data;
node* next;
public:
node(int data):data(data)
{
next=NULL;
}
friend class LinkedList;
};
class LinkedList{
node* head;
static int lengthRecursiveHelper(node* node)
{
if(!node)
return 0;
return 1+lengthRecursiveHelper(node->next);
}
static node* merge(node* head1, node* head2)
{
node* head=NULL;
node* prev=NULL;
while(head1!=NULL && head2!=NULL)
{
if(head1->data<head2->data)
{
//cout<<head1->data<<" ";
if(head==NULL)
head=head1;
else
prev->next=head1;
prev=head1;
head1=head1->next;
}
else
{
//cout<<head2->data<<" ";
if(head==NULL)
head=head2;
else
prev->next=head2;
prev=head2;
head2=head2->next;
}
}
while(head1)
{
// cout<<head1->data<<" ";
prev->next=head1;
prev=head1;
head1=head1->next;
}
while(head2)
{
// cout<<head2->data<<" ";
prev->next=head2;
prev=head2;
head2=head2->next;
}
return head;
}
static int findElementRHelper(node* head, int data)
{
if(!head)
return -1;
else if(head->data==data)
return 0;
int ans=findElementRHelper(head->next, data);
if(ans==-1)
return -1;
else
return 1+ ans;
}
node* midPointNode()
{
if(!head) return NULL;
node* fast=head;
node* slow=head;
while(fast->next && fast->next->next)
{
fast=fast->next->next;
slow=slow->next;
}
return slow;
}
public:
LinkedList():head(NULL) {
}
void addAtBegin(int a){
node* newNode=new node(a);
newNode->next=head;
head=newNode;
}
int len(){
int len=0;
node* temp=head;
while(temp!=NULL)
{
len++;
temp=temp->next;
}
return len;
}
int lengthRecursive(){
return lengthRecursiveHelper(head);
}
void insertAtEnd(int data){
node* newNode= new node(data);
if(head==NULL)
{head=newNode;
return;}
node* temp=head;
while(temp->next!=NULL)
{
temp=temp->next;
}
temp->next=newNode;
}
LinkedList & operator=(LinkedList const & b){
this->head=NULL;
node* temp=b.head;
node* prev=NULL;
while(temp!=NULL)
{ node* newNode=new node(temp->data);
if(this->head==NULL)
this->head=newNode;
else prev->next=newNode;
prev=newNode;
temp=temp->next;
}
//return *this;
}
LinkedList & operator+=(LinkedList const & b){
node* temp=this->head;
while(temp->next!=NULL)
temp=temp->next;
node* temp2=b.head;
while(temp2!=NULL)
{
node* newNode=new node(temp2->data);
temp->next=newNode;
temp=temp->next;
temp2=temp2->next;
}
return *this;
}
void deleteAtIth(int i)
{
int len=this->len();
if(i>=len)
{
cout<<"there aren't enough eleemnts"<<endl;
return;
}
if(i==0)
{
node* temp=head->next;
delete temp;
head=head->next;
return;
}
int currPos=0;
node* temp=head;
while(currPos<i-1)
{
temp=temp->next;
currPos++;
}
node* temp2=temp->next->next;
delete temp->next;
temp->next=temp2;
}
void insertAtIth(int data, int i){
if(i==0)
{
this->addAtBegin(data);
return;
}
int currentPos=0;
node* temp=this->head;
while(currentPos<i-1)
{
currentPos++;
temp=temp->next;
if(temp==NULL) break;
}
if(temp==NULL)
{
cout<<"Index too large"<<endl;
return;
}
node* newNode=new node(data);
newNode->next=temp->next;
temp->next=newNode;
}
void deleteAtBegin(){
if(!head) return;
node* temp=head->next;
delete head;
head=temp;
}
LinkedList & operator+(int x){
node* newNode=new node(x);
if (this->head==NULL)
this->head=newNode;
node* temp=this->head;
while(temp->next!=NULL)
temp=temp->next;
temp->next=newNode;
return *this;
}
/* LinkedList add(LinkedList const & b) {
LinkedList *c=new LinkedList;
LinkedList addRecursiveHelper(*this, b, c);
return *c;
}
*/
int midPoint(){
if(!head) return -1;
node* midNode=midPointNode();
return midNode->data;
}
void bubbleSort(){
int l=len();
for(int i=0; i<l; i++)
{
node* current=head;
node* prev=NULL;
while(current && current->next)
{
if(current->data>current->next->data)
{
if(prev==NULL)
{
node* nextNode=current->next;
current->next=current->next->next;
nextNode->next=current;
head=nextNode;
prev=nextNode;
}
else
{
node* nextNode=current->next;
current->next=current->next->next;
prev->next=nextNode;
nextNode->next=current;
prev=nextNode;
}
}
else
{
prev=current;
current=current->next;
}
}
}
}
void deleteAtEnd(){
if(!head)
return;
if(head->next==NULL)
{
delete head;
head=NULL;
return;
}
node* temp=head;
while(temp->next->next!=NULL)
{
temp=temp->next;
}
node* temp2=temp->next;
delete temp2;
temp->next=NULL;
}
void print() const{
node*temp=head;
while(temp!=NULL)
{
cout<<temp->data<<" --> ";
temp=temp->next;
}
cout<<endl;
}
LinkedList(LinkedList const & s){
this->head=NULL;
node* temp=s.head;
node* prev=NULL;
while(temp!=NULL)
{
node* newNode=new node(temp->data);
if(this->head==NULL)
this->head=newNode;
else
prev->next=newNode;
prev=newNode;
temp=temp->next;
}
}
LinkedList operator+(LinkedList const & b) {
LinkedList *output=new LinkedList(*this);
int len=this->len();
node* temp=b.head;
while(temp!=NULL)
{
output->insertAtIth(temp->data, len);
temp=temp->next;
len++;
}
return *output;
}
bool findElement(int data)
{
node* temp=head;
while(temp!=NULL)
{
if(temp->data==data)
return true;
temp=temp->next;
}
return false;
}
int findPosition(int data)
{
node* temp=head;
int pos=0;
while(temp!=NULL)
{
if(temp->data==data)
return pos;
temp=temp->next;
pos++;
}
return -1;
}
int findElementR(int data)
{
return findElementRHelper(head, data);
}
int midPointer()
{
node* slow=head;
node* fast=head;
while(fast && fast->next && fast->next->next)
{
slow=slow->next;
fast=fast->next->next;
}
return slow->data;
}
static LinkedList retainAndMerge(LinkedList const & a, LinkedList const & b)
{
LinkedList LinkedListM;
node* prev=NULL;
node* temp1=a.head;
node* temp2=b.head;
while(temp1!=NULL && temp2!=NULL)
{
if(temp1->data<temp2->data)
{
cout<<temp1->data<<" ";
node* newNode=new node(temp1->data);
if(!LinkedListM.head)
LinkedListM.head=newNode;
else
prev->next=newNode;
prev=newNode;
temp1=temp1->next;
}
else
{
cout<<temp2->data<<" ";
node* newNode=new node(temp2->data);
if(!LinkedListM.head)
LinkedListM.head=newNode;
else
prev->next=newNode;
prev=newNode;
temp2=temp2->next;
}
}
while(temp1!=NULL)
{
cout<<temp1->data<<" ";
node* newNode=new node(temp1->data);
prev->next=newNode;
prev=newNode;
temp1=temp1->next;
}
while(temp2!=NULL)
{
cout<<temp2->data<<" ";
node* newNode=new node(temp2->data);
prev->next=newNode;
prev=newNode;
temp2=temp2->next;
}
return LinkedListM;
}
static LinkedList merge(LinkedList & a, LinkedList & b)
{
LinkedList c;
node *newHead=merge(a.head, b.head);
c.head=newHead;
a.head=NULL; b.head=NULL;
return c;
}
static LinkedList deleteAndMerge(LinkedList & a, LinkedList & b)
{
LinkedList newLL;
node* prev=NULL;
node* temp1=a.head;
node* temp2=b.head;
while(temp1 && temp2)
{
if(temp1->data<temp2->data)
{
if(newLL.head==NULL)
newLL.head=temp1;
else
prev->next=temp1;
prev=temp1;
temp1=temp1->next;
}
else
{
if(newLL.head==NULL)
newLL.head=temp2;
else
prev->next=temp2;
prev=temp2;
temp2=temp2->next;
}
}
while(temp1)
{
prev->next=temp1;
prev=temp1;
temp1=temp1->next;
}
while(temp2)
{
prev->next=temp2;
prev=temp2;
temp2=temp2->next;
}
a.head=NULL;
b.head=NULL;
return newLL;
}
};
void takeInput(LinkedList &a)
{
int temp;
// cout<<"Enter next"<<endl;
cin>>temp;
while(temp!=-1)
{
a.addAtBegin(temp);
// cout<<"Enter next"<<endl;
cin>>temp;
}
}
int main() {
LinkedList a;
takeInput(a);
a.print();
LinkedList b;
takeInput(b);
b.print();
LinkedList c=LinkedList::merge(a, b);
cout<<endl;
c.print();
a.print();
b.print();
// cout<<a.midPointer()<<endl;
// cout<<a.midPoint()<<endl;
// cout<<a.findElement(5)<<endl;
// cout<<a.findPosition(5)<<endl;
// cout<<a.findElementR(5)<<endl;
// a.bubbleSort();
// a.print();
/*a.addAtBegin(5);
a.insertAtIth(6,1);
a.insertAtEnd(8);
a.print();
/*LinkedList b=a;
b.print();
b.deleteAtIth(1);
b.print();
a.print();
LinkedList c;
c.addAtBegin(1);
c.print();
(c+5).print();
c.print();
c.deleteAtBegin();
c.print();
a.print();
LinkedList d=a+b;
d.print();
d+1;
d.print();
d.deleteAtEnd();
d.print();
*/
return 0;
}