fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. class Node {
  5. public:
  6. 	int data;
  7. 	Node* next;
  8. };
  9.  
  10. int getCount(Node* head);
  11.  
  12. int _getIntesectionNode(int d, Node* head1, Node* head2);
  13.  
  14. int getIntesectionNode(Node* head1, Node* head2)
  15. {
  16. 	int c1 = getCount(head1);
  17. 	int c2 = getCount(head2);
  18. 	int d;
  19.  
  20. 	if (c1 > c2) {
  21. 		d = c1 - c2;
  22. 		return _getIntesectionNode(d, head1, head2);
  23. 	}
  24. 	else {
  25. 		d = c2 - c1;
  26. 		return _getIntesectionNode(d, head2, head1);
  27. 	}
  28. }
  29.  
  30. int _getIntesectionNode(int d, Node* head1, Node* head2)
  31. {
  32. 	Node* current1 = head1;
  33. 	Node* current2 = head2;
  34.  
  35. 	for (int i = 0; i < d; i++) {
  36. 		if (current1 == NULL) {
  37. 			return -1;
  38. 		}
  39. 		current1 = current1->next;
  40. 	}
  41.  
  42. 	while (current1 != NULL && current2 != NULL) {
  43. 		if (current1 == current2)
  44. 			return current1->data;
  45.  
  46. 		current1 = current1->next;
  47. 		current2 = current2->next;
  48. 	}
  49.  
  50. 	return -1;
  51. }
  52.  
  53. int getCount(Node* head)
  54. {
  55. 	Node* current = head;
  56.  
  57. 	int count = 0;
  58.  
  59. 	while (current != NULL) {
  60. 		count++;
  61. 		current = current->next;
  62. 	}
  63. 	return count;
  64. }
  65.  
  66. int main()
  67. {
  68. 	Node* newNode;
  69. 	Node* head1 = new Node();
  70. 	head1->data = 9;
  71.  
  72. 	Node* head2 = new Node();
  73. 	head2->data = 8;
  74.  
  75. 	newNode = new Node();
  76. 	newNode->data = 10;
  77. 	head2->next = newNode;
  78.  
  79. 	newNode = new Node();
  80. 	newNode->data = 5;
  81. 	head2->next->next = newNode;
  82.  
  83. 	newNode = new Node();
  84. 	newNode->data = 15;
  85. 	head1->next = newNode;
  86. 	head2->next->next->next = newNode;
  87.  
  88. 	newNode = new Node();
  89. 	newNode->data = 20;
  90. 	head1->next->next = newNode;
  91.  
  92. 	head1->next->next->next = NULL;
  93.  
  94. 	cout << "The node of intersection is " << getIntesectionNode(head1, head2);
  95. }
Success #stdin #stdout 0.01s 5436KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
The node of intersection is 15
https://ideone.com/RB0fp5
language:
C++ (gcc 8.3)
created:
3 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!