Train Track Merge Point Detection

A railway company is analyzing its train routes and wants to determine if two train tracks merge at any station. Each train route is represented as a singly linked list, where each node represents a station, and the next pointer links to the next station on the route.

The company has given you two train routes (linked lists) and wants to return the name(value of node) of the first common station where the routes merge. If the routes do not merge, return the string No merging station.

Your task is to implement a function getMergingStation that finds the first station where the routes merge and returns a string.

You are ONLY allowed to modify the getMergingStation function. You are NOT allowed to modify the given template.

NOTE: The linked lists are constructed such that if there is a merging point, the nodes from that point onward are the same objects in memory (i.e., the two lists share the exact same node instances starting from the merging station).

Input Format

• The first input line contains m space-separated strings, where each string represents a unique station name in Train Route A.
• The second input line contains n space-separated strings, where each string represents a unique station name in Train Route B.
• Next three lines contain integers required to create linked lists (You don't need to use these inputs).

Constraints

• 1 ≤ m, n ≤ 10^7 (Each train route has at most 10^7 stations)

Output Format

• Return Merge at if the routes merge at some station.
• Return No merging station if they do not merge.

Sample Input 0

31 39 56 34 32 96 35 17 48 51 52 70 97 16 76 38
11 8 50 12 19 68 37 20 10 5 98 43 84 53 79 87 77 54 57 90 70 97 16 76 38
1
11
20

Sample Output 0

Merge at 70

Sample Input 1

47 43 7 91 9 14 38 54 1 11 25 8 46 39
64 41 81 83 90 67 87 27 22 18 25 8 46 39
1
10
10

Solution

Solution by Sangeeth

#include <iostream>
#include <unordered_set>
#include <vector>
#include <sstream>

using namespace std;

struct ListNode {
    string val;
    ListNode* next;
    ListNode(string x) : val(x), next(nullptr) {}
};

string getMergingStation(ListNode* headA, ListNode* headB) {
    vector <int> listA;
    vector<int> listB;
      while (headA != nullptr) {
        listA.push_back(stoi(headA->val));
        headA = headA->next;
    }

     while (headB != nullptr) {
        listB.push_back(stoi(headB->val));
        headB = headB->next;
    }






   int i = listA.size() - 1;
    int j = listB.size() - 1;
    int intersectionPoint = -1; // Default value if no intersection

    while (i >= 0 && j >= 0) {
        if (listA[i] == listB[j]) {
            intersectionPoint = listA[i];
            i--;
            j--;
        }  else {
           break;
        }
    }



    if (intersectionPoint== -1){
        return "No merging station";
    }
    else {return "Merge at " + to_string(intersectionPoint) ;}
    /* Enter your code here. */
}

ListNode* createLinkedLists(string intersect_val, vector<string>& listA_vals, vector<string>& listB_vals, int skipA, int skipB, ListNode*& headB) {
    if (listA_vals.empty() || listB_vals.empty()) return nullptr;

    vector<ListNode*> nodesA;

    for (const string& val : listA_vals) nodesA.push_back(new ListNode(val));
    for (size_t i = 0; i < nodesA.size() - 1; ++i) nodesA[i]->next = nodesA[i + 1];
    ListNode* headA = nodesA[0];

    if (intersect_val == "0") {
        vector<ListNode*> nodesB;
        for (const string& val : listB_vals) nodesB.push_back(new ListNode(val));
        for (size_t i = 0; i < nodesB.size() - 1; ++i) nodesB[i]->next = nodesB[i + 1];
        headB = nodesB[0];
    } else {
        vector<ListNode*> nodesB;
        int s = listB_vals.size();
        for (int i = 0; i < skipB && i < s; ++i) nodesB.push_back(new ListNode(listB_vals[i]));
        for (size_t i = 0; i < nodesB.size() - 1; ++i) nodesB[i]->next = nodesB[i + 1];
        headB = nodesB.empty() ? nullptr : nodesB[0];

        int n_s = nodesA.size();
        ListNode* intersection_node = (skipA < n_s) ? nodesA[skipA] : nullptr;
        if (!nodesB.empty() && intersection_node) nodesB.back()->next = intersection_node;
        else if (nodesB.empty()) headB = intersection_node;
    }
    return headA;
}

int main() {
    vector<string> listA_vals, listB_vals;
    string station;

    string inputA, inputB;
    getline(cin, inputA);
    getline(cin, inputB);

    istringstream streamA(inputA), streamB(inputB);
    while (streamA >> station) listA_vals.push_back(station);
    while (streamB >> station) listB_vals.push_back(station);

    string intersect_val;
    cin >> intersect_val;

    int skipA, skipB;
    cin >> skipA >> skipB;

    ListNode* headA;
    ListNode* headB;
    headA = createLinkedLists(intersect_val, listA_vals, listB_vals, skipA, skipB, headB);

    cout << getMergingStation(headA, headB) << endl;
    return 0;
}