首页 > 试题广场 >

给定两个升序线性表L1和L2,设计一个函数,将两个升序线性表

[问答题]

给定两个升序线性表L1和L2,设计一个函数,将两个升序线性表合并为一个升序线性表L,新线性表L中无重复数据。

//合并单链表
//先合并再去重
ListNode* Merge(ListNode* L1, ListNode* L2)
{
    //链表为空的特殊情况
    if (L1 == nullptr && L2 == nullptr)
    {
        return L1;
    }
    //合并操作
    ListNode *dummy = new ListNode(0), *cur = dummy;
    while (L1 != nullptr && L2 != nullptr)
    {
        if (L1->data < L2->data)
        {
            cur->next = L1;
            L1 = L1->next;
        }
        else if (L1->data > L2->data)
        {
            cur->next = L2;
            L2 = L2->next;
        }
        else
        {
            cur->next = L1;
            L1 = L1->next;
            L2 = L2->next;
        }
        cur = cur->next;
    }
    cur->next = L1 != nullptr ? L1:L2;
    //去重操作
    ListNode* pos = dummy->next;//定义前驱结点
    while(pos->next != nullptr)
    {
        cur = pos->next;
        //printf("pos->data=%d,cur->data=%d\n",pos->data,cur->data);
        if (pos->data != cur->data)
        {
            pos = pos->next;
        }
        else
        {
            pos->next = pos->next->next;
        }
    }
    pos->next = nullptr;
    return dummy;
}
写得比较菜仅供参考。
这里参考了力扣的方法:

发表于 2021-04-19 00:20:40 回复(0)
算法参考归并排序,归并的那一部分
发表于 2020-11-22 18:37:36 回复(1)