数据结构| |链表面试题之求两个链表的交集和差集

175 阅读 0 评论 116 点赞

我是靠谱客的博主魔幻月饼，这篇文章主要介绍数据结构| |链表面试题之求两个链表的交集和差集，现在分享给大家，希望可以做个参考。

这个面试题简单看代码就可理解。

//求两个链表的交集
pList Intersection(pList pList1, pList pList2)
{
    if (pList1 == NULL || pList2 == NULL)
    {
        return NULL;
    }
    pList newList = BuyNode(0);//添加头结点，这样就不用在后面进行第一次找相等的节点了，可以统一查找
    pNode tail = newList;
    while (pList1 != NULL && pList2 != NULL)
    {
        //两个数值相等，两个链表同时向后移动一个结点
        if (pList1->data == pList2->data)
        {
            tail->next = pList1;
            tail = pList1;
            pList1 = pList1->next;
            pList2 = pList2->next;
        }
        //pList1->data < pList2->data,pList1向后移动结点
        else if (pList1->data < pList2->data)
        {
            pList1 = pList1->next;
        }
        else
        {
            pList2 = pList2->next;
        }
    }
    return newList;
}

//求两个链表的差集
pList Difset(pList pList1, pList pList2)
{
    if (pList1 == NULL)
    {
        return pList2;
    }
    if (pList2 == NULL)
    {
        return pList1;
    }
    //直接给一个带有头结点的链表，取得差集
    pList newList = BuyNode(0);
    pNode tail = newList;
    while (pList1 != NULL && pList2 != NULL)
    {
        if (pList1->data == pList2->data)
        {
            pList1 = pList1->next;
            pList2 = pList2->next;
        }
        else if (pList1->data < pList2->data)
        {
            tail->next = pList1;
            tail = pList1;
            pList1 = pList1->next;
        }
        else
        {
            tail->next = pList2;
            tail = pList2;
            pList2 = pList2->next;
        }
    }
    if (pList1 != NULL)
    {
        tail->next = pList1;
    }
    else
    {
        tail->next = pList2;
    }
    return newList;
}