/****************************************************
* Section : 15
* Machine No. : N
* Roll No. : 19CS100XY
* Name : Aritra Hazra
* Assignment No : 10a
* Description : Intersect and Merge Two Linked Lists
                (Stoppage Stations of Trains)
*****************************************************/

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

typedef struct nodeType {
    int data;
    struct nodeType *next;
}node;

/* generating first linked list */
node *genSeq1(int n)
{
    node *L, *p;
    /* Create the fist node to store n */
    L = (node *)malloc(sizeof(node));
    L->data = n;
    /* Initialize the running pointer p for subsequent insertions */
    p = L;
    while( n ) { /* As long as n is not reduced to zero */
        /* Compute the next value of n */
        n -= (int)sqrt((double)n);
        /* Allocate memory */
        p->next = (node *)malloc(sizeof(node));
        /* Store n in the new node, and advance */
        p = p->next;
        p->data = n;
    }
    p -> next = NULL; /* Terminate the list */
    return L; /* Return the header */
}

/* generating second linked list and merging it at the common node with first list */
node *genSeq2(node *T1, int n)
{
    node *T2, *p1, *p2;
    /* Skip values in the first list larger than n */
    p1 = T1;
    while(p1->data > n)
        p1 = p1->next;
    /* If n is already present in the first list */
    if(p1->data == n)
        return p1;
    /* Create the fist node in the second list to store n */
    T2 = (node *)malloc(sizeof(node));
    T2->data = n;
    /* Initialize the running pointer p for subsequent insertions */
    p2 = T2;
    while(1) { /* Let us decide to return inside the loop */
        n -= (int)sqrt((double)n); /* Next value of n */
        /* p1 skips all values in the first list, larger than the current n */
        while((p1 != NULL) && (p1->data > n))
            p1 = p1->next;
        if(p1->data == n) { /* n found in first list */
            p2->next = p1 ; /* Adjust the second list */
            return T2; /* Return header to second list */
        }
        /* n not found in first list, so create a new node in second list */
        p2->next = (node *)malloc(sizeof(node));
        p2 = p2->next;
        p2->data = n;
    }
}

/* finding the intersection node (merging point) between two list */
node *getIntersection(node *T1, node *T2)
{
    node *p1, *p2;
    p1 = T1 ; p2 = T2 ; /* Initialize pointers */
    while(1) { /* Return inside the loop */
        /* If the common node is located, return an appropriate pointer */
        if(p1->data == p2->data)
            return p1;
        /* else if p1 points to a larger integer than p2 */
        else if(p1->data > p2->data)
            p1 = p1->next;
        else p2 = p2->next;
    }
}

int main()
{
    int n1, n2;
    node *T1, *T2, *nodePtr, *intersectNode;
    
    printf("Enter Starting Stoppage Number (ID) for Train-1: ");
    scanf("%d", &n1);
    printf("Enter Starting Stoppage Number (ID) for Train-2: ");
    scanf("%d", &n2);
    T1 = genSeq1(n1);
    printf("\nStoppages (ID) for Train-1:\nT1");
    for(nodePtr=T1; nodePtr != NULL; nodePtr=nodePtr->next){
        printf(" --> [ %d ]", nodePtr->data);
    }
    printf("--> X\n");
    T2 = genSeq2(T1, n2);
    printf("\nStoppages (ID) for Train-2:\nT2");
    for(nodePtr=T2; nodePtr != NULL; nodePtr=nodePtr->next){
        printf(" --> [ %d ]", nodePtr->data);
    }
    printf("--> X\n");
    intersectNode = getIntersection(T1, T2);
    printf("\nIntersect Stoppage ID --> [ %d ]\n", intersectNode->data);

    return 0;
}