fork download
copy 
  1. // Given two linked list find and print the intersection of these two.
  2. #include<iostream>
  3. using namespace std;
  4. class node
  5. {
  6. public:
  7. 	int data;
  8. 	node* next; 
  9. 	node(int data){
  10. 		this->data = data;
  11. 		next = NULL;
  12. 	}
  13.  
  14. };
  15. void InsertAtTail(node *&head, int data){
  16. 	if(head==NULL){
  17. 		head = new node(data);
  18. 		return;
  19. 	}
  20. 	node *temp = head;
  21. 	while(temp->next!=NULL){
  22. 		temp = temp->next;
  23. 	}
  24. 	temp->next = new node(data);
  25. 	return;
  26. }
  27. node* Intersection(node *a, node *b){
  28. 	node *temp = NULL;
  29. 	while(a!=NULL && b!=NULL){
  30. 		if(a->data==b->data){
  31. 			InsertAtTail(temp,a->data);
  32. 			a = a->next;
  33. 			b = b->next;
  34. 		}
  35. 		else if(a->data<b->data){
  36. 			a = a->next;
  37. 		}
  38. 		else{
  39. 			b = b->next;
  40. 		}
  41. 	}
  42. 	return temp;
  43. }
  44. node* IntersectionRecursive(node *a, node *b, node *&temp){
  45. 	if(a==NULL || b==NULL){
  46. 		return temp;
  47. 	}
  48. 	if(a->data==b->data){
  49. 		InsertAtTail(temp,a->data);
  50. 		return IntersectionRecursive(a->next,b->next,temp);
  51. 	}
  52. 	else if(a->data<b->data){
  53. 		return IntersectionRecursive(a->next,b,temp);
  54. 	}
  55. 	else{
  56. 		return IntersectionRecursive(a,b->next,temp);
  57. 	}
  58. }
  59. // Following commented function is not working! The dummy concept is not working here!.
  60. // node* SortedIntersection(node *a, node *b){
  61. // 	node dummy;
  62. // 	node *temp = &dummy;
  63. // 	while(a!=NULL && b!=NULL){
  64. // 		if(a->data==b->data){
  65. // 			InsertAtTail(temp->next,a->data);
  66. // 			temp = temp->next;
  67. // 			a = a->next;
  68. // 			b = b->next;
  69. // 		}
  70. // 		else if(a->data<b->data){
  71. // 			a = a->next;
  72. // 		}
  73. // 		else{
  74. // 			b = b->next;
  75. // 		}
  76. // 	}
  77. // 	return temp->next;
  78. // }
  79. void printLL(node *head){
  80. 	while(head!=NULL){
  81. 		cout<<head->data;
  82. 		if(head->next!=NULL){
  83. 			cout<<"->";
  84. 		}
  85. 		head = head->next;
  86. 	}
  87. 	cout<<endl;
  88. }
  89. int main()
  90. {
  91. 	node *first = NULL;
  92. 	node *second = NULL;
  93. 	int n,data;
  94. 	cin>>n;
  95. 	for(int i=0;i<n;i++){
  96. 		cin>>data;
  97. 		InsertAtTail(first,data);
  98. 	}
  99. 	cin>>n;
  100. 	for(int i=0;i<n;i++){
  101. 		cin>>data;
  102. 		InsertAtTail(second,data);
  103. 	}
  104. 	node *temp = NULL;
  105. 	temp = Intersection(first,second);
  106. 	// temp = IntersectionRecursive(first,second,temp);
  107. 	// temp = SortedIntersection(a,b,temp);
  108. 	printLL(temp);
  109. 	return 0;
  110. }
Success #stdin #stdout 0s 4388KB
comments (?)
stdin
copy 
5
1 2 4 5 8
4
1 3 4 5
stdout
copy 
1->4->5
https://ideone.com/wVgwb8
language:
C++14 (gcc 8.3)
created:
5 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!