45 lines
1.5 KiB
C++
45 lines
1.5 KiB
C++
/**
|
|
* 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);
|
|
}
|
|
};
|