fork download
copy 
  1. #include <iostream>
  2. using namespace std;
  3. struct node{
  4. 	      int data;
  5. 	      struct node* next;
  6. };
  7. struct node* createnode(int val)
  8. {
  9. 	struct node* p=(struct node*)malloc(sizeof(struct node));
  10. 	p->data=val;
  11. 	p->next=NULL;
  12. 	return p;
  13. }
  14. struct node* split(struct node* head)
  15. {
  16. 	struct node* fast=head;
  17. 	struct node* slow=head;
  18. 	while(fast!=NULL && fast->next!=NULL)
  19. 	{
  20. 	fast=fast->next->next;
  21. 	if(fast!=NULL)
  22. 	slow=slow->next;
  23. 	}
  24. 	struct node* temp=slow->next;
  25. 	slow->next=NULL;
  26. 	return temp;
  27. }
  28. struct node* merge(struct node* first,struct node* second)
  29. {
  30. 	if(first==NULL)
  31. 	return second;
  32.     if(second==NULL)
  33. 	return first;
  34. 	if(first->data<second->data)
  35. 	{
  36. 		first->next=merge(first->next,second);
  37. 		return first;
  38. 	}
  39. 	else
  40. 	{
  41. 		second->next=merge(first,second->next);
  42. 		return second;
  43. 	}
  44. }
  45.  
  46. struct node* mergesort(struct node* head)
  47. {
  48. 	if(head==NULL ||head->next==NULL)
  49. 	return head;
  50. struct node* second=split(head);
  51. head=mergesort(head);
  52. second=mergesort(second);
  53. return merge(head,second);
  54.  
  55. }
  56. void printlinked(struct node* head)
  57. {
  58. 	while(head!=NULL)
  59. 	{
  60. 		cout<<head->data<< " ";
  61. 		head=head->next;
  62. 	}
  63. }
  64. int main() {
  65. 	struct node* head=createnode(5);
  66. 	head->next=createnode(12);
  67. 	head->next->next=createnode(10);
  68. 	head->next->next->next=createnode(8);
  69. 	head->next->next->next->next=createnode(8);
  70. 	struct node* result=mergesort(head);
  71. 	printlinked(result);
  72. 	return 0;
  73. }
Success #stdin #stdout 0.01s 5272KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
5 8 8 10 12
https://ideone.com/qkPOip
language:
C++ (gcc 8.3)
created:
9 days 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!