leetcode-160

leetcode 160 相交链表

题目描述：相交链表

方法

1. 哈希表

   先遍历链表A，用哈希表记录下所有出现过的节点的地址。然后再遍历链表B，逐个判断节点是否在哈希表中。第一个在哈希表中出现的节点便是公共结点。

2. 双指针

   无论两个链表是否相交，它们的最后一个节点的next域肯定指向nullptr，因此可以假设存在一个nulptr节点，作为两个链表的公共节点。即：两个链表尾部至少存在一个nullptr的公共节点。

   所谓双指针，就是让指针pA先遍历链表A，指针pB先遍历链表B。对每一个指针，在遍历到链表末尾时切换到另一个链表的头部接着遍历。

   假设两个链表的长度分别为n和m，那么两个指针一定会在走n+m步时相遇。

   如果两个链表本身有公共节点，那么两个指针只会提前相遇（小于n+m步就相遇）

题解代码

哈希表

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB)
{
    unordered_set<ListNode*> visited; // 此处用set也能过，但是没有unordered_set快
    auto* p = headA;
    while(p){
        visited.insert(p);
        p=p->next;
    }
    p = headB;
    while(p){
        if(visited.count(p)){
            return p;
        }
        p = p->next;
    }
    return p;
}

双指针

// 双指针
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB)
{
    if (!headA || !headB)
    {
        return nullptr;
    }
    auto *pA = headA;
    auto *pB = headB;
    while (pA != pB)
    {
        if (!pA)
        {
            pA = headB;
        }
        else
        {
            pA = pA->next;
        }

        if (!pB)
        {
            pB = headA;
        }
        else
        {
            pB = pB->next;
        }
    }
    return pA;
}