142.环形链表 II

两天宇宙人

2020-02-19

🐶双指针

相当于将两个链表连在一起，一条是A + B, 一条是B + A，走过同样的长度。

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode* a = headA, *b = headB;
        while(a != b) {
            a = a == nullptr ? headB : a->next;
            b = b == nullptr ? headA : b->next;
        }
        return a;
    }
};

🚌set实现

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if(!head)
            return nullptr;
        set<ListNode*> st;
        st.insert(head);
        while(head) {
            head = head->next;
            if(!head) 
                return nullptr;
            if(st.count(head)) {
                return head;
            } else {
                st.insert(head);
            }
        }
        return nullptr;
    }
};