fork download
copy 
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. class LinkedList;
  5.  
  6. class node{
  7. 	int data;
  8. 	node* next;
  9.  
  10. 	public:
  11. 	node(int data):data(data)
  12. 	{
  13. 		next=NULL;
  14. 	}
  15. 	friend class LinkedList;
  16. };
  17.  
  18. class LinkedList{
  19. 	node* head;
  20. 	static int lengthRecursiveHelper(node* node)
  21. 	{
  22. 		if(!node)
  23. 			return 0;
  24. 		return 1+lengthRecursiveHelper(node->next);
  25. 	}
  26.  
  27. 	static node* merge(node* head1, node* head2)
  28. 	{
  29. 		node* head=NULL;
  30. 		node* prev=NULL;
  31. 		while(head1!=NULL && head2!=NULL)
  32. 		{
  33. 			if(head1->data<head2->data)
  34. 		{
  35. 			//cout<<head1->data<<"  ";
  36. 			if(head==NULL)
  37. 				head=head1;
  38. 			else
  39. 				prev->next=head1;
  40. 			prev=head1;
  41. 			head1=head1->next;
  42. 		}
  43. 		else
  44. 		{
  45. 			//cout<<head2->data<<" ";
  46. 			if(head==NULL)
  47. 				head=head2;
  48. 			else
  49. 				prev->next=head2;
  50. 			prev=head2;
  51. 			head2=head2->next;
  52. 		}
  53. 		}
  54. 		while(head1)
  55. 		{
  56. 		//	cout<<head1->data<<" ";
  57. 			prev->next=head1;
  58. 			prev=head1;
  59. 			head1=head1->next;
  60. 		}
  61.  
  62. 		while(head2)
  63. 		{
  64. 		//	cout<<head2->data<<" ";
  65. 			prev->next=head2;
  66. 			prev=head2;
  67. 			head2=head2->next;
  68. 		}
  69. 		return head;
  70. 	}
  71.  
  72.  
  73. 	static int findElementRHelper(node* head, int data)
  74. 	{
  75. 		if(!head)
  76. 			return -1;
  77. 		else if(head->data==data)
  78. 			return 0;
  79.  
  80. 		int ans=findElementRHelper(head->next, data);
  81. 		if(ans==-1)
  82. 			return -1;
  83. 		else
  84. 			return 1+ ans;
  85. 	}
  86.  
  87. 	node* midPointNode()
  88. 	{
  89. 		if(!head) return NULL;
  90. 		node* fast=head;
  91. 		node* slow=head;
  92. 		while(fast->next && fast->next->next)
  93. 		{
  94. 			fast=fast->next->next;
  95. 			slow=slow->next;
  96. 		}
  97. 		return slow;
  98. 	}
  99.  
  100. 	public:
  101. 	LinkedList():head(NULL)	{
  102. 	}
  103.  
  104. 	void addAtBegin(int a){
  105. 		node* newNode=new node(a);
  106. 		newNode->next=head;
  107. 		head=newNode;
  108. 	}
  109.  
  110. 	int len(){
  111. 		int len=0;
  112. 		node* temp=head;
  113. 		while(temp!=NULL)
  114. 		{
  115. 			len++;
  116. 			temp=temp->next;
  117. 		}
  118. 		return len;
  119. 	}
  120.  
  121. 	int lengthRecursive(){
  122. 		return lengthRecursiveHelper(head);
  123. 	}
  124.  
  125. 	void insertAtEnd(int data){
  126. 		node* newNode= new node(data);
  127. 		if(head==NULL)
  128. 			{head=newNode;
  129. 			return;}
  130. 		node* temp=head;
  131. 		while(temp->next!=NULL)
  132. 		{
  133. 			temp=temp->next;
  134. 		}
  135. 		temp->next=newNode;
  136. 	}
  137.  
  138. 	LinkedList & operator=(LinkedList const & b){
  139. 		this->head=NULL;
  140. 		node* temp=b.head;
  141. 		node* prev=NULL;
  142. 		while(temp!=NULL)
  143. 		{	node* newNode=new node(temp->data);
  144. 			if(this->head==NULL)
  145. 				this->head=newNode;
  146. 			else prev->next=newNode;
  147. 			prev=newNode;
  148. 			temp=temp->next;
  149. 		}
  150. 		//return *this;
  151. 	}
  152.  
  153. 	LinkedList & operator+=(LinkedList const & b){
  154. 		node* temp=this->head;
  155. 		while(temp->next!=NULL)
  156. 			temp=temp->next;
  157. 		node* temp2=b.head;
  158. 		while(temp2!=NULL)
  159. 		{
  160. 			node* newNode=new node(temp2->data);
  161. 			temp->next=newNode;
  162. 			temp=temp->next;
  163. 			temp2=temp2->next;
  164. 		}
  165. 		return *this;
  166. 	}
  167.  
  168. 	void deleteAtIth(int i)
  169. 	{
  170. 		int len=this->len();
  171. 		if(i>=len)
  172. 		{
  173. 			cout<<"there aren't enough eleemnts"<<endl;
  174. 			return;
  175. 		}
  176.  
  177. 		if(i==0)
  178. 		{
  179. 		node* temp=head->next;
  180. 		delete temp;
  181. 		head=head->next;
  182. 		return;
  183. 		}
  184.  
  185. 		int currPos=0;
  186. 		node* temp=head;
  187. 		while(currPos<i-1)
  188. 		{
  189. 			temp=temp->next;
  190. 			currPos++;
  191. 		}
  192. 		node* temp2=temp->next->next;
  193. 		delete temp->next;
  194. 		temp->next=temp2;
  195.  
  196. 	}
  197.  
  198. 	void insertAtIth(int data, int i){
  199. 		if(i==0)
  200. 		{
  201. 			this->addAtBegin(data);
  202. 			return;
  203. 		}
  204.  
  205. 		int currentPos=0;
  206. 		node* temp=this->head;
  207. 		while(currentPos<i-1)
  208. 		{
  209. 			currentPos++;
  210. 			temp=temp->next;
  211. 			if(temp==NULL) break;
  212. 		}
  213.  
  214. 		if(temp==NULL)
  215. 		{
  216. 			cout<<"Index too large"<<endl;
  217. 			return;
  218. 		}
  219.  
  220. 		node* newNode=new node(data);
  221. 		newNode->next=temp->next;
  222. 		temp->next=newNode;
  223. 	}
  224.  
  225. 	void deleteAtBegin(){
  226. 		if(!head) return;
  227. 		node* temp=head->next;
  228. 		delete head;
  229. 		head=temp;
  230. 	}
  231.  
  232. 	LinkedList & operator+(int x){
  233. 		node* newNode=new node(x);
  234. 		if (this->head==NULL)
  235. 			this->head=newNode;
  236. 		node* temp=this->head;
  237. 		while(temp->next!=NULL)
  238. 			temp=temp->next;
  239.  
  240. 		temp->next=newNode;
  241. 		return *this;
  242. 	}
  243.  
  244. /*	LinkedList add(LinkedList const & b) {
  245. 		LinkedList *c=new LinkedList;
  246. 		LinkedList addRecursiveHelper(*this, b, c);
  247. 		return *c;
  248. 	}
  249.  
  250. */	
  251. 	int midPoint(){
  252. 		if(!head) 	return -1;
  253. 		node* midNode=midPointNode();
  254. 		return midNode->data;
  255. 	}
  256.  
  257. 	void bubbleSort(){
  258. 		int l=len();
  259. 		for(int i=0; i<l; i++)
  260. 		{
  261. 			node* current=head;
  262. 			node* prev=NULL;
  263. 			while(current && current->next)
  264. 			{
  265. 				if(current->data>current->next->data)
  266. 				{
  267. 					if(prev==NULL)
  268. 					{
  269. 						node* nextNode=current->next;
  270. 						current->next=current->next->next;
  271. 						nextNode->next=current;
  272. 						head=nextNode;
  273. 						prev=nextNode;
  274. 					}
  275. 					else
  276. 					{
  277. 						node* nextNode=current->next;
  278. 						current->next=current->next->next;
  279. 						prev->next=nextNode;
  280. 						nextNode->next=current;
  281. 						prev=nextNode;
  282. 					}
  283. 				}
  284. 				else
  285. 				{
  286. 					prev=current;
  287. 					current=current->next;
  288. 				}
  289. 			}
  290. 		}
  291. 	}
  292.  
  293. 	void deleteAtEnd(){
  294. 		if(!head)
  295. 		return;
  296.  
  297. 		if(head->next==NULL)
  298. 		{
  299. 			delete head;
  300. 			head=NULL;
  301. 			return;
  302. 		}
  303.  
  304. 		node* temp=head;
  305. 		while(temp->next->next!=NULL)
  306. 		{
  307. 			temp=temp->next;
  308. 		}
  309.  
  310. 		node* temp2=temp->next;
  311. 		delete temp2;
  312. 		temp->next=NULL;
  313. 	}
  314.  
  315. 	void print() const{
  316. 		node*temp=head;
  317. 		while(temp!=NULL)
  318. 		{
  319. 			cout<<temp->data<<" --> ";
  320. 			temp=temp->next;
  321. 		}
  322. 		cout<<endl;
  323. 	}
  324.  
  325. 	LinkedList(LinkedList const & s){
  326. 		this->head=NULL;
  327. 		node* temp=s.head;
  328. 		node* prev=NULL;
  329. 		while(temp!=NULL)
  330. 		{
  331. 			node* newNode=new node(temp->data);
  332. 			if(this->head==NULL)
  333. 				this->head=newNode;
  334. 			else
  335. 				prev->next=newNode;
  336. 			prev=newNode;
  337. 			temp=temp->next;
  338. 		}
  339. 	}
  340.  
  341. 	LinkedList operator+(LinkedList const & b) {
  342. 		LinkedList *output=new LinkedList(*this);
  343. 		int len=this->len();
  344. 		node* temp=b.head;
  345. 		while(temp!=NULL)
  346. 		{
  347. 			output->insertAtIth(temp->data, len);
  348. 			temp=temp->next;
  349. 			len++;
  350. 		}
  351. 		return *output;
  352. 	}
  353.  
  354. 	bool findElement(int data)
  355. 	{
  356. 		node* temp=head;
  357. 		while(temp!=NULL)
  358. 		{
  359. 			if(temp->data==data)
  360. 			return true;
  361. 			temp=temp->next;
  362. 		}
  363. 		return false;
  364. 	}
  365.  
  366. 	int findPosition(int data)
  367. 	{
  368. 		node* temp=head;
  369. 		int pos=0;
  370. 		while(temp!=NULL)
  371. 		{
  372. 			if(temp->data==data)
  373. 				return pos;
  374. 				temp=temp->next;
  375. 				pos++;
  376. 		}
  377. 		return -1;
  378. 	}
  379.  
  380. 	int findElementR(int data)
  381. 	{
  382. 		return findElementRHelper(head, data);
  383. 	}
  384.  
  385. 	int midPointer()
  386. 	{
  387. 		node* slow=head;
  388. 		node* fast=head;
  389. 		while(fast && fast->next && fast->next->next)
  390. 		{
  391. 			slow=slow->next;
  392. 			fast=fast->next->next;
  393. 		}
  394. 		return slow->data;
  395. 	}
  396.  
  397.  
  398. static LinkedList retainAndMerge(LinkedList const & a, LinkedList const & b)
  399. 	{
  400. 		LinkedList LinkedListM;
  401. 		node* prev=NULL;
  402. 		node* temp1=a.head;
  403. 		node* temp2=b.head;
  404. 		while(temp1!=NULL && temp2!=NULL)
  405. 		{
  406. 			if(temp1->data<temp2->data)
  407. 			{
  408. 				cout<<temp1->data<<"   ";
  409. 				node* newNode=new node(temp1->data);
  410. 				if(!LinkedListM.head)
  411. 					LinkedListM.head=newNode;
  412. 				else
  413. 					prev->next=newNode;
  414. 				prev=newNode;
  415. 				temp1=temp1->next;
  416. 			}
  417. 			else
  418. 			{
  419. 				cout<<temp2->data<<"  ";
  420. 				node* newNode=new node(temp2->data);
  421. 				if(!LinkedListM.head)
  422. 					LinkedListM.head=newNode;
  423. 				else
  424. 					prev->next=newNode;
  425. 				prev=newNode;
  426. 				temp2=temp2->next;
  427. 			}
  428. 		}
  429.  
  430. 			while(temp1!=NULL)
  431. 			{
  432. 				cout<<temp1->data<<"  ";
  433. 				node* newNode=new node(temp1->data);
  434. 				prev->next=newNode;
  435. 				prev=newNode;
  436. 				temp1=temp1->next;
  437. 			}
  438.  
  439. 			while(temp2!=NULL)
  440. 			{	
  441. 				cout<<temp2->data<<"  ";
  442. 				node* newNode=new node(temp2->data);
  443. 				prev->next=newNode;
  444. 				prev=newNode;
  445. 				temp2=temp2->next;
  446. 			}
  447.  
  448. 			return LinkedListM;
  449. 	}
  450.  
  451. static LinkedList merge(LinkedList & a, LinkedList & b)
  452. {
  453. 	LinkedList c;
  454. 	node *newHead=merge(a.head, b.head);
  455. 	c.head=newHead;
  456. 	a.head=NULL; b.head=NULL;
  457. 	return c;
  458. }
  459.  
  460. static LinkedList deleteAndMerge(LinkedList & a, LinkedList & b)
  461. {
  462. 	LinkedList newLL;
  463. 	node* prev=NULL;
  464. 	node* temp1=a.head;
  465. 	node* temp2=b.head;
  466.  
  467. 	while(temp1 && temp2)
  468. 	{
  469. 		if(temp1->data<temp2->data)
  470. 		{
  471. 			if(newLL.head==NULL)
  472. 				newLL.head=temp1;
  473. 			else
  474. 				prev->next=temp1;
  475. 				prev=temp1;
  476. 				temp1=temp1->next;
  477. 		}
  478. 		else
  479. 		{
  480. 			if(newLL.head==NULL)
  481. 				newLL.head=temp2;
  482. 			else
  483. 				prev->next=temp2;
  484. 				prev=temp2;
  485. 				temp2=temp2->next;
  486. 		}
  487. 	}
  488.  
  489. 	while(temp1)
  490. 	{
  491. 		prev->next=temp1;
  492. 		prev=temp1;
  493. 		temp1=temp1->next;
  494. 	}
  495.  
  496. 	while(temp2)
  497. 	{
  498. 		prev->next=temp2;
  499. 		prev=temp2;
  500. 		temp2=temp2->next;
  501. 	}
  502. 	a.head=NULL;
  503. 	b.head=NULL;
  504. 	return newLL;
  505. }
  506.  
  507. };
  508.  
  509. void takeInput(LinkedList &a)
  510. {
  511. 	int temp;
  512. //	cout<<"Enter next"<<endl;
  513. 	cin>>temp;
  514. 	while(temp!=-1)
  515. 	{
  516. 	a.addAtBegin(temp);
  517. //	cout<<"Enter next"<<endl;
  518. 	cin>>temp;
  519. 	}
  520. }
  521.  
  522. int main() {
  523. 	LinkedList a;
  524. 	takeInput(a);
  525. 	a.print();
  526. 	LinkedList b;
  527. 	takeInput(b);
  528. 	b.print();
  529. 	LinkedList c=LinkedList::merge(a, b);
  530. 	cout<<endl;
  531. 	c.print();
  532. 	a.print();
  533. 	b.print();
  534.  
  535. //	cout<<a.midPointer()<<endl;
  536. //	cout<<a.midPoint()<<endl;
  537. //	cout<<a.findElement(5)<<endl;
  538. //	cout<<a.findPosition(5)<<endl;
  539. //	cout<<a.findElementR(5)<<endl;
  540. //	a.bubbleSort();
  541. //	a.print();
  542.  
  543. 	/*a.addAtBegin(5);
  544. 	a.insertAtIth(6,1);
  545. 	a.insertAtEnd(8);
  546. 	a.print();
  547. 	/*LinkedList b=a;
  548. 	b.print();
  549. 	b.deleteAtIth(1);
  550. 	b.print();
  551. 	a.print();
  552. 	LinkedList c;
  553. 	c.addAtBegin(1);
  554. 	c.print();
  555. 	(c+5).print();
  556. 	c.print();
  557. 	c.deleteAtBegin();
  558. 	c.print();
  559. 	a.print();
  560. 	LinkedList d=a+b;
  561. 	d.print();
  562. 	d+1;
  563. 	d.print();
  564. 	d.deleteAtEnd();
  565. 	d.print();
  566. 	*/
  567. 	return 0;
  568. }
  569.  
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
4
3
2
1
-1
9
8
7
6
-1
stdout
copy 
1 --> 2 --> 3 --> 4 --> 
6 --> 7 --> 8 --> 9 --> 

1 --> 2 --> 3 --> 4 --> 6 --> 7 --> 8 --> 9 -->
https://ideone.com/rsP6R7
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!