[已解决]用与n无关的方法删除队列的特定元素？

小X学X森

最佳答案

月排行榜 / 总排行榜

＜（￥＿＄）＞

2017-11-16 10:33:22

给你一个时间复杂度为o(1)的方案，还没调试，大概思路是这样的

typedef int ElementType;

struct ListNode
{
    struct ListNode *m_pNext;
    ElementType m_Data;
};

void DeleteNode(ListNode *pListHead, ListNode *pToBeDeleted)
{
    assert(pListHead != NULL && pToBeDeleted != NULL);

    if (pToBeDeleted->m_pNext != NULL) //说明还有后继结点
    {
        ListNode *pTmp = pToBeDeleted->m_pNext;

        //直接把后一个结点赋值给要删除的结点
        pToBeDeleted->m_Data = pTmp->m_Data;
        pToBeDeleted->m_pNext = pTmp->m_pNext;

        //然后删除下一个结点
        free(pTmp);
    }
    else if (pListHead != pToBeDeleted) //如果没有后继结点，而且不是头结点
    {
        ListNode *pTmp = pListHead;

        while (pTmp != NULL)
        {
            //找到要删除结点的前一个
            if (pTmp->m_pNext = pToBeDeleted)
            {
                //删除pToBeDeleted结点
                pTmp->m_pNext = pToBeDeleted->m_pNext;
                free(pToBeDeleted);
                break;
            }
        }
    }
    else //说明程序只有头结点，删除的也是头结点
    {
        free(pToBeDeleted);
        pListHead = NULL; //这里这个形参被办法返回，所以这个函数的参数定义的有点问题
    }
}

跳转到最佳答案楼层

＜（￥＿＄）＞

给你一个时间复杂度为o(1)的方案，还没调试，大概思路是这样的

typedef int ElementType;

struct ListNode
{
    struct ListNode *m_pNext;
    ElementType m_Data;
};

void DeleteNode(ListNode *pListHead, ListNode *pToBeDeleted)
{
    assert(pListHead != NULL && pToBeDeleted != NULL);

    if (pToBeDeleted->m_pNext != NULL) //说明还有后继结点
    {
        ListNode *pTmp = pToBeDeleted->m_pNext;

        //直接把后一个结点赋值给要删除的结点
        pToBeDeleted->m_Data = pTmp->m_Data;
        pToBeDeleted->m_pNext = pTmp->m_pNext;

        //然后删除下一个结点
        free(pTmp);
    }
    else if (pListHead != pToBeDeleted) //如果没有后继结点，而且不是头结点
    {
        ListNode *pTmp = pListHead;

        while (pTmp != NULL)
        {
            //找到要删除结点的前一个
            if (pTmp->m_pNext = pToBeDeleted)
            {
                //删除pToBeDeleted结点
                pTmp->m_pNext = pToBeDeleted->m_pNext;
                free(pToBeDeleted);
                break;
            }
        }
    }
    else //说明程序只有头结点，删除的也是头结点
    {
        free(pToBeDeleted);
        pListHead = NULL; //这里这个形参被办法返回，所以这个函数的参数定义的有点问题
    }
}

小X学X森

新手求帮助最好写下代码，嫌烦的话给点思路也可以

BngThea

用无限循环依次遍历各个节点，对数据和目标进行匹配判断，判断成功就删去该节点，然后跳出循环

小X学X森

BngThea 发表于 2017-11-16 11:13
用无限循环依次遍历各个节点，对数据和目标进行匹配判断，判断成功就删去该节点，然后跳出循环

队列不能在中间直接删除一个元素的吧？可是如果队列中没有这个点的话要怎么退出循环呢

BngThea

小X学X森 发表于 2017-11-16 12:25
队列不能在中间直接删除一个元素的吧？可是如果队列中没有这个点的话要怎么退出循环呢

看你给的函数形参形式，应该是操作一个链表吧，所以中间删去一个节点应该很容易办到

而题目中强调了是队列中的一个特定的元素，所以目标元素肯定是存在于队列中的

Brance

遍历链表，如果发现链表某个节点和该待删节点的属性匹配，删除之。
具体图为：

                               
登录/注册后可看大图

SixPy

如果只是链表，做不到与n无关。
不过 python里有 OrderedDict，有序字典。
它既像字典那样直接操作元素，又像链表那样保持元素的插入次序。

zqianglh

小X学X森 发表于 2017-11-16 12:25
队列不能在中间直接删除一个元素的吧？可是如果队列中没有这个点的话要怎么退出循环呢

if(前驱->next->data==特定) {
temp=前驱->next
前驱->next =前驱->next->next
free(temp); }

SixPy

＜（￥＿＄）＞ 发表于 2017-11-19 12:46
给你一个时间复杂度为o(1)的方案，还没调试，大概思路是这样的

没看出来，怎么就O(1) 了？

＜（￥＿＄）＞

SixPy 发表于 2017-11-23 12:39
没看出来，怎么就O(1) 了？

如果不是尾节点，只要将后一个结点赋值给要删除的结点，然后删除后一个结点，这个时间复杂度为o(1)应该没什么疑问，对于尾节点，那遍历时跑不掉了，那对于尾节点来说，时间复杂度为o(n)，那总的时间复杂度为o(1)应该就没啥疑问了吧