36 lines
1.3 KiB
C++
36 lines
1.3 KiB
C++
/**
|
|
* Definition for singly-linked list.
|
|
*/
|
|
#include <cstddef>
|
|
struct ListNode {
|
|
int val;
|
|
ListNode *next;
|
|
ListNode(int x) : val(x), next(NULL) {}
|
|
};
|
|
|
|
// I couldn't figure this solution out on my own, so I looked it up on YouTube.
|
|
// This is my implementation after seeing the method.
|
|
// The idea is to use two pointers, and advance both forwards; if the end is reached by either,
|
|
// swap that pointer to the beginning of the opposite list.
|
|
// Once both pointers have moved all the way to the end, they will be in line with each other;
|
|
// by this token, some time before they even reach the end, they will reach their common intersection point,
|
|
// and be equal to each other.
|
|
//
|
|
// Even if they don't intersect, they will still end up equal to each other, both as null pointers.
|
|
//
|
|
// P.S. for reasons unknown, solution B that I wrote seems to consistently work faster,
|
|
// despite being asymptotically slower; and it doesn't even have simpler operations, either.
|
|
// I don't know what the cause could be, but...
|
|
class Solution {
|
|
public:
|
|
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
|
|
ListNode* a = headA;
|
|
ListNode* b = headB;
|
|
while (a != b) {
|
|
a = a == nullptr ? headB : a->next;
|
|
b = b == nullptr ? headA : b->next;
|
|
}
|
|
return a;
|
|
}
|
|
};
|