fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // Data Structure to store a linked list node
  5. struct Node
  6. {
  7. 	int data;
  8. 	Node* next;
  9. };
  10.  
  11. // Helper function to print given linked list
  12. void printList(struct Node* head)
  13. {
  14. 	struct Node* ptr = head;
  15. 	while (ptr)
  16. 	{
  17. 		cout << ptr->data << " -> ";
  18. 		ptr = ptr->next;
  19. 	}
  20.  
  21. 	cout << "nullptr\n";
  22. }
  23.  
  24. // Helper function to insert a new node in the beginning of the linked list
  25. void push(struct Node** headRef, int data)
  26. {
  27. 	struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
  28. 	newNode->data = data;
  29. 	newNode->next = *headRef;
  30. 	*headRef = newNode;
  31. }
  32.  
  33. // Compute a new sorted list that represents the intersection of the
  34. // two given sorted lists. This solution uses the local reference
  35. struct Node* SortedIntersect(struct Node* a, struct Node* b)
  36. {
  37. 	struct Node *head = nullptr;
  38. 	struct Node* tail = nullptr;
  39.  
  40. 	while (a != nullptr && b != nullptr) {
  41. 		if (a->data == b->data) {
  42. 			if(head == nullptr) {
  43. 				push(&head, a->data);
  44. 				tail=head;
  45. 			} else {
  46. 				push(&tail->next, a->data);
  47. 				tail=tail->next;
  48. 			}
  49.  
  50. 			a = a->next;
  51. 			b = b->next;
  52. 		} else if (a->data < b->data)
  53. 			a = a->next;
  54. 		else
  55. 			b = b->next;
  56. 	}
  57. 	return head;
  58. }
  59.  
  60. // main method
  61. int main()
  62. {
  63. 	// input keys
  64. 	int keys[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
  65. 	int n = sizeof(keys)/sizeof(keys[0]);
  66.  
  67. 	struct Node *a = nullptr;
  68. 	for (int i = n - 1; i >=0; i = i - 3)
  69. 		push(&a, keys[i]);
  70.  
  71.     struct Node *b = nullptr;
  72. 	for (int i = n - 1; i >=0; i = i - 2)
  73. 		push(&b, keys[i]);
  74.  
  75.     // print both linked list
  76. 	cout << "First List  - ";
  77. 	printList(a);
  78.  
  79. 	cout << "Second List - ";
  80. 	printList(b);
  81.  
  82. 	struct Node *head = SortedIntersect(a, b);
  83.  
  84. 	cout << "\nAfter Intersection - ";
  85. 	printList(head);
  86.  
  87. 	return 0;
  88. }
  89.  
Success #stdin #stdout 0s 3468KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
First List  - 1 -> 4 -> 7 -> 10 -> nullptr
Second List - 2 -> 4 -> 6 -> 8 -> 10 -> nullptr

After Intersection - 4 -> 10 -> nullptr
https://ideone.com/zhqRPZ
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!