/**
 * Definition for singly-linked list.
 */
#include <cstddef>
#include <vector>
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

// This solution is now O(n) time and O(n) space.
// The method is to copy the linked list nodes into two vectors;
// then, starting from the back, if the elements are not equal from the very end,
// the lists don't intersect ever.
// Otherwise, iterating from the back, find the first node that isn't shared between the lists,
// and then return the node just after that (which is shared by both).
// If we get all the way to the beginning, then the first node of the lists must be the shared one.
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        std::vector<ListNode*> listA;
        std::vector<ListNode*> listB;
        for (ListNode* start = headA; start != nullptr; start = start->next) {
            listA.push_back(start);
        }
        for (ListNode* start = headB; start != nullptr; start = start->next) {
            listB.push_back(start);
        }
        int endA = listA.size() - 1;
        int endB = listB.size() - 1;
        if (listA.at(endA) != listB.at(endB)) {
            return nullptr;
        }
        while (endA >= 0 && endB >= 0) {
            if (listA.at(endA) != listB.at(endB)) {
                return listA.at(endA + 1);
            }
            endA--;
            endB--;
        }
        return listA.at(endA + 1);
    }
};