fork download
copy 
  1. //
  2. //  main.cpp
  3. //  Intersection Point
  4. //
  5. //  Created by Himanshu on 03/10/21.
  6. //
  7.  
  8.  
  9. #include <iostream>
  10. using namespace std;
  11.  
  12. struct node {
  13.     int info = 0;
  14.     struct node *next;
  15. };
  16. typedef struct node Node;
  17.  
  18. node* newNode(int data)
  19. {
  20.     node* Node = new node();
  21.     Node->info = data;
  22.     Node->next = NULL;
  23.  
  24.     return(Node);
  25. }
  26.  
  27. void printLinkedList (Node* head) {
  28.     Node *x = head;
  29.  
  30.     while (x != NULL) {
  31.         cout<<(x->info)<<" ";
  32.         x = x->next;
  33.     }
  34.     cout<<endl;
  35. }
  36.  
  37. Node* insertNode (Node *head, Node* x) {
  38.     Node *node = head;
  39.     while (node->next != NULL) {
  40.         node = node->next;
  41.     }
  42.     x->next = NULL;
  43.     node->next = x;
  44.     return head;
  45. }
  46.  
  47. Node* searchNode (Node *head, int k) {
  48.     Node* x = head;
  49.  
  50.     while (x != NULL && x->info != k) {
  51.         x = x->next;
  52.     }
  53.  
  54.     if (x != NULL && x->info == k) {
  55.         return x;
  56.     } else {
  57.         return NULL;
  58.     }
  59. }
  60.  
  61. int findListLength (Node *head) {
  62.     int len = 0;
  63.     Node *node = head;
  64.     while (node != NULL) {
  65.         len++;
  66.         node = node->next;
  67.     }
  68.     return len;
  69. }
  70.  
  71. Node* solve (Node *head1, Node *head2) {
  72.     Node *node1 = head1, *node2 = head2;
  73.     int len1 = findListLength(head1), len2 = findListLength(head2);
  74.     int diff = len1 - len2;
  75.  
  76.     if (len1 < len2) {
  77.         node1 = head2;
  78.         node2 = head1;
  79.         diff = len2 - len1;
  80.     }
  81.  
  82.     for (int i=0; i<diff; i++) {
  83.         node1 = node1->next;
  84.     }
  85.  
  86.     while (node1 != node2) {
  87.         node1 = node1->next;
  88.         node2 = node2->next;
  89.     }
  90.  
  91.     return node1;
  92. }
  93.  
  94. int main() {
  95.     Node *head1 = newNode(1);
  96.     Node *head2 = newNode(9);
  97.  
  98.     head1 = insertNode (head1, newNode(2));
  99.     head1 = insertNode (head1, newNode(3));
  100.     head1 = insertNode (head1, newNode(4));
  101.     head1 = insertNode (head1, newNode(8));
  102.  
  103.     head2 = insertNode (head2, newNode(5));
  104.     head2 = insertNode (head2, newNode(7));
  105.  
  106.     Node *x = searchNode(head2, 7);
  107.     x->next = searchNode(head1, 4);
  108.  
  109.     cout<<"Linked List 1:"<<endl;
  110.     printLinkedList(head1);
  111.  
  112.     cout<<"Linked List 2:"<<endl;
  113.     printLinkedList(head2);
  114.  
  115.     x = solve(head1, head2);
  116.  
  117.     if (x) {
  118.         cout<<"Intersection point is: "<<(x->info)<<endl;
  119.     } else {
  120.         cout<<"No intersection point found"<<endl;
  121.     }
  122.  
  123.     return 0;
  124. }
  125.  
  126.  
Success #stdin #stdout 0.01s 5428KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Linked List 1:
1 2 3 4 8 
Linked List 2:
9 5 7 4 8 
Intersection point is: 4
https://ideone.com/zwssLW
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
secret

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!