160. Intersection of Two Linked Lists

O(m+n) time O(1) space

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        auto n1 = headA, n2 = headB;
        while (n1 != n2) {
            n1 = n1 ? n1->next : headB; // 注意要判断n1是不是为空，最后有可能根本没有交点，则两个指针都落在nullptr上
            n2 = n2 ? n2->next : headA;
        }
        return n1;
    }
};

如果有cycle又不能用hashmap

struct Node {
    Node(int x) : val(x) {}
    Node *next = nullptr;
};

Node *getCycle(Node *head) {
    auto fast = head, slow = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) break;
    }
    if (!fast || !fast->next) return nullptr;
    slow = head;
    while (slow != fast) {
        slow = slow->next;
        fast = fast->next;
    }
    return slow;
}

bool f(Node *headA, Node *headB) {
    auto a = getCycle(headA), b = getCycle(headB);
    if (a && b) return a == b;
    if (!a && !b) {
        while (headA != headB) {
            headA = headA ? headA->next : headB;
            headB = headB ? headB->next : headA;
        }
        return headA;
    }
    return false;
}