精华内容
下载资源
问答
  • 之前,小编已经写了如何在单链表中删除第一个节点不是数字‘2’ 代码,那现在改变题目一下,就是如何删除单链表最后一个节点不是数字‘2’。其实,思路跟删除第一个节点有点相似,就是得用递归来traverse到最后...

    之前,小编已经写了如何在单链表中删除第一个节点不是数字‘2’ 的代码,那现在改变题目一下,就是如何删除单链表中最后一个节点不是数字‘2’。

    其实,思路跟删除第一个节点有点相似,就是得用递归来traverse到最后一个节点,然后进行判断最后一个节点是否是数字‘2’。

    下面是list.h 文件里代码展示

    //list.h
    #include<iostream>
    #include<cstring>
    #include<cctype>
    
    using namespace std;
    
    struct node
    {
        int data;
        node * next;
    };
    
    class list
    {
        public:
            //These function are already written
            list();
            ~list();
            void build();
            void display();
    
            //This is the prototype for this question
            //Remove the last node if the last node is not 2
            void remove_last();
    
        private:
            //Remove the last node if the last node is not 2
            void remove_last(node *& tail, node * head);
    
            node * head;
            node * tail;
    };

    我相信,很多人就会觉得直接用tail指针来判断最后一个节点是否是2,如果不是2,那就直接删除,那tail指针就得指向倒数第二个节点上,不然就会出seg fault,所以就得用head指针来进行traverse到倒数第二个节点上,来进行判断最后一个节点。因为是更改链表,就得pass by reference,不能pass by value,所以在prototype上写的是node *& tail。

    下面是实现这个函数的代码展示:

    //list.cpp
    #include "list.h"
    
    void list::remove_last()
    {
        remove_last(tail,head);
    }
    
    void list::remove_last(node *& tail, node * head)
    {
        if(!head)
            return;
        if(!head->next->next)
        {
            if(head->next->data != 2)
            {
                delete head->next;
                head->next = NULL;
                tail = head;
                return;
            }
            else
                return;
        }
        remove_last(tail,head->next);
    }

    上面就是如何实现这道题的代码,感觉是不是挺简短精辟呢!其实递归就是能使代码量缩小的,而且能让别人很清楚你的思路是什么样的。

    下面是结果展示:
    结果展示

    如果最后一个节点是2的话,就不删除,结果同样展示出来给你们看看:
    结果展示

    是不是感觉很神奇呢,递归就是这么神奇!

    下次,小编还会继续使用递归来实现不同数据结构中的不同功能,敬请期待哦!

    记得为小编点赞哦!!

    展开全文
  • 链表中有多个节点,链表的最后一个节点将被删除。1. 链表中只有一个节点条件head → next = NULL将继续存在,因此,链表的唯一节点head将被指定为null。 这将通过使用以下语句来完成。ptr = head;head = NULL;free...

    从链表的末尾删除节点,有两种情况。

    链表中只有一个节点,需要删除。

    链表中有多个节点,链表的最后一个节点将被删除。

    1. 链表中只有一个节点

    条件head → next = NULL将继续存在,因此,链表的唯一节点head将被指定为null。 这将通过使用以下语句来完成。

    ptr = head;

    head = NULL;

    free(ptr);

    2. 链表中有多个节点

    条件head→next = NULL将失败,因此,必须遍历节点才能到达链表的最后一个节点。

    为此,只需声明一个临时指针temp并将其指定给链表的头部。还需要跟踪链表的倒数第二个节点。所以使用两个指针ptr和ptr1,其中ptr将指向最后一个节点,ptr1将指向链表的倒数第二个节点。通过使用以下语句来完成。

    ptr = head;

    while(ptr->next != NULL)

    {

    ptr1 = ptr;

    ptr = ptr ->next;

    }

    现在,只需要使指针ptr1指向下一个节点为NULL,并且ptr将变释放。它将通过使用以下语句来完成。

    ptr1->next = NULL;

    free(ptr);

    算法

    第1步:IF HEAD = NULL

    打印内存溢出。

    转到第8步

    [结束]

    第2步:设置PTR = HEAD

    第3步:重复第4步和第5步,同时PTR - > NEXT!= NULL

    第4步:SET PREPTR = PTR

    第5步:SET PTR = PTR - > NEXT

    [循环结束]

    第6步:SET PREPTR - > NEXT = NULL

    第7步:释放PTR

    第8步:退出

    示意图 -

    03c9f4d169360c87a9e47b33676f5b7d.png

    C语言示例代码 -

    #include

    #include

    void create(int);

    void end_delete();

    struct node

    {

    int data;

    struct node *next;

    };

    struct node *head;

    void main()

    {

    int choice, item;

    do

    {

    printf("1.Append List\n");

    printf("2.Delete node\n");

    printf("3.Exit\n");

    printf("4.Enter your choice ? ");

    scanf("%d", &choice);

    switch (choice)

    {

    case 1:

    printf("\nEnter the item\n");

    scanf("%d", &item);

    create(item);

    break;

    case 2:

    end_delete();

    break;

    case 3:

    exit(0);

    break;

    default:

    printf("\nPlease enter valid choice\n");

    }

    } while (choice != 3);

    }

    void create(int item)

    {

    struct node *ptr = (struct node *)malloc(sizeof(struct node *));

    if (ptr == NULL)

    {

    printf("\nOVERFLOW\n");

    }

    else

    {

    ptr->data = item;

    ptr->next = head;

    head = ptr;

    printf("\nNode inserted\n");

    }

    }

    void end_delete()

    {

    struct node *ptr, *ptr1;

    if (head == NULL)

    {

    printf("\nlist is empty");

    }

    else if (head->next == NULL)

    {

    head = NULL;

    free(head);

    printf("\nOnly node of the list deleted ...");

    }

    else

    {

    ptr = head;

    while (ptr->next != NULL)

    {

    ptr1 = ptr;

    ptr = ptr->next;

    }

    ptr1->next = NULL;

    free(ptr);

    printf("\n Deleted Node from the last ...");

    }

    }

    执行上面示例代码,得到以下结果 -

    1.Append List

    2.Delete node

    3.Exit

    4.Enter your choice?1

    Enter the item

    12

    Node inserted

    1.Append List

    2.Delete node

    3.Exit

    4.Enter your choice?2

    Only node of the list deleted ...

    ¥ 我要打赏

    纠错/补充

    收藏

    上一篇:链表

    下一篇:双链表

    加QQ群啦,易百教程官方技术学习群

    注意:建议每个人选自己的技术方向加群,同一个QQ最多限加 3 个群。

    展开全文
  • 设一个没有头结点指针的单链表,有一指针指向此单链表中一个结点(非第一个,也非最后一个结点),将该结点从单链表删除,要求时间复杂度O(1)。 没有头指针,则不可能遍历该单链表,况且要求时间复杂度为是常数,...

    设一个没有头结点指针的单链表,有一指针指向此单链表中一个结点(非第一个,也非最后一个结点),将该结点从单链表中删除,要求时间复杂度O(1)。
    没有头指针,则不可能遍历该单链表,况且要求时间复杂度为是常数,则可交换要删除节点(p)和该节点的下一个节点(p->next)的数据域,然后问题转换为删除p节点的下一个节点。
    q=p->next;
    p->data=q->data;
    p->next=q->next;
    free(q);

    展开全文
  • 一个指针指向此单链表中间一个节点(既不是第一个,也不是最后一个节点),请将该节点从单链表删除。 p->data = p->next->data; p->next = p->next->next; firee(p->next);    链表结点定义...

    问题:假设一个没有头指针的单链表。一个指针指向此单链表中间的一个节点(既不是第一个,也不是最后一个节点),请将该节点从单链表中删除。

    p->data = p->next->data;

    p->next = p->next->next;

    firee(p->next); 

     

    链表结点定义如下:

    struct ListNode

    {

             int       m_nKey;

             ListNode* m_pNext;

    };

    解答:假设给定的指针为pCurrent,ListNode* pNext = pCurrent->m_pNext;

    由题意知,pCurrent指向链表的某一个中间节点,因此pCurrent->m_pNext != NULL。

    要删除pCurrent指向的节点B很简单,但必须将节点B前后两个节点A和C连接起来,但是单链表节点没有头指针,因此无法追溯到A,也就无法将A和C相连了。

    无法删除节点B,但我们可以删除B的后继节点C,并通过pCurrent->m_pNext = pCurrent->m_pNext->m_pNext重新将链表连接起来,而唯一丢失的是节点C的数据项m_nKey。因此,我们只需要将节点C的数据项取代节点B的数据项,然后将真正指向节点C的指针删除即可实现将节点B“删除”!!关键代码如下:

    pCurrent->m_pNext = pNext->m_pNext;

    pCurrent->m_nKey = pNext->m_nKey;

    delete pNext;

    完整代码如下:

    #include <iostream>

    #include <assert.h>

    struct ListNode

    {

        int m_nKey;

        ListNode* m_pNext;      

    };

    //参数必须是指向指针的指针,因为要修改指针

    //所以要考虑“参数本地拷贝”问题

    void InitList(ListNode** pList)

    {

         *pList = (ListNode*)malloc(sizeof(ListNode));

         (*pList)->m_pNext = NULL;

    }

    //第一个参数不必是指向指针的指针,因为函数内只修改指针指向的数据

    //所以不用担心“参数本地拷贝”问题

    void InsertList(ListNode* pList, int data)

    {

        ListNode* pNewNode = (ListNode*)malloc(sizeof(ListNode));

        pNewNode->m_nKey = data;

        pNewNode->m_pNext = pList->m_pNext;

        pList->m_pNext = pNewNode;

    }

    //核心算法

    void DeleteRandomNode(ListNode* pCurrent)

    {

        assert(pCurrent != NULL);

        ListNode* pNext = pCurrent->m_pNext;

        if(pNext != NULL)

        {

            pCurrent->m_pNext = pNext->m_pNext;

            pCurrent->m_nKey = pNext->m_nKey;

            delete pNext;      

                       pNext = NULL;

        }    

    }

    //打印链表元素

    void PrintListNormally(ListNode* pListHead)

    {

        ListNode* pTempNode = pListHead->m_pNext;

        while(pTempNode != NULL)

        {

            std::cout<<pTempNode->m_nKey<<std::endl;

            pTempNode = pTempNode->m_pNext;            

        }    

    }

    int main()

    {

        ListNode* pHead = NULL;

        InitList(&pHead);

        for(int i=9; i>=0; i--)

        {

            InsertList(pHead,i);       

        }

        PrintListNormally(pHead);

        ListNode* pNext = pHead->m_pNext->m_pNext; //删除第个元素

        DeleteRandomNode(pNext);

        PrintListNormally(pHead);

        system("pause");

        return 0;   

    }

    =======================================================

    扩展题目:给定链表的头指针和一个结点指针,在O(1)时间删除该结点。链表结点的定义如下:

    struct ListNode

    {

             int        m_nKey;

             ListNode*  m_pNext;

    };

    函数的声明如下:

    void DeleteNode(ListNode* pListHead, ListNode* pToBeDeleted);

    分析:这是一道广为流传的Google面试题,能有效考察我们的编程基本功,还能考察我们的反应速度,更重要的是,还能考察我们对时间复杂度的理解。

    在链表中删除一个结点,最常规的做法是从链表的头结点开始,顺序查找要删除的结点,找到之后再删除。由于需要顺序查找,时间复杂度自然就是O(n) 了。

    我们之所以需要从头结点开始查找要删除的结点,是因为我们需要得到要删除的结点的前面一个结点。我们试着换一种思路。我们可以从给定的结点得到它的下一个结点。这个时候我们实际删除的是它的下一个结点,由于我们已经得到实际删除的结点的前面一个结点,因此完全是可以实现的。当然,在删除之前,我们需要需要把给定的结点的下一个结点的数据拷贝到给定的结点中。此时,时间复杂度为O(1)。

    上面的思路还有一个问题:如果删除的结点位于链表的尾部,没有下一个结点,怎么办?我们仍然从链表的头结点开始,顺便遍历得到给定结点的前序结点,并完成删除操作。这个时候时间复杂度是O(n)。

    那题目要求我们需要在O(1)时间完成删除操作,我们的算法是不是不符合要求?实际上,假设链表总共有n个结点,我们的算法在n-1总情况下时间复杂度是O(1),只有当给定的结点处于链表末尾的时候,时间复杂度为O(n)。那么平均时间复杂度[(n-1)*O(1)+O(n)]/n,仍然为O(1)。

    基于前面的分析,我们不难写出下面的代码。

    核心参考代码:

    //核心算法

    //pListHead是链表头指针,pCurrent是要删除的节点指针

    void DeleteRandomNode(ListNode* pListHead, ListNode* pCurrent)

    {

        assert(pCurrent != NULL || pListHead != NULL);

        if(pCurrent->m_pNext != NULL) //要删除的节点不是最后一个节点

        {

            ListNode* pNext = pCurrent->m_pNext;

            pCurrent->m_nKey = pNext->m_nKey;

            pCurrent->m_pNext = pNext->m_pNext;

            delete pNext;

            pNext = NULL;                   

        }

        else //要删除的节点是链表中最后一个节点

        {

            ListNode* pNode = pListHead;

            while(pNode->m_pNext != pCurrent) //得到要删除节点的前继节点

            {

                pNode = pNode->m_pNext;                    

            }

            pNode->m_pNext = NULL;

            delete pCurrent;

            pCurrent = NULL;

        }

    }

    完整的代码只需替换第一题的相应函数,并在main函数调用中做相应修改即可。

    值得注意的是,为了让代码看起来简洁一些,上面的代码基于两个假设:(1)给定的结点的确在链表中;(2)给定的要删除的结点不是链表的头结点。不考虑第一个假设对代码的鲁棒性是有影响的。至于第二个假设,当整个列表只有一个结点时,代码会有问题。但这个假设不算很过分,因为在有些链表的实现中,会创建一个虚拟的链表头,并不是一个实际的链表结点。这样要删除的结点就不可能是链表的头结点了。当然,在面试中,我们可以把这些假设和面试官交流。这样,面试官还是会觉得我们考虑问题很周到的。

    本文来自CSDN博客,转载请标明出处:http://blog.csdn.NET/ACE1985/archive/2010/08/06/5793287.aspx


    展开全文
  • 6-3 删除单链表最后一个与给定值相等结点 (10分) 本题要求在链表中删除最后一个数据域取值为x的节点。L是一个带头结点单链表,函数ListLocateAndDel_L(LinkList L, ElemType x)要求在链表中查找最后一个数据域...
  • 6-3 删除单链表最后一个与给定值相等结点 (10分) 本题要求在链表中删除最后一个数据域取值为x的节点。L是一个带头结点单链表,函数ListLocateAndDel_L(LinkList L, ElemType x)要求在链表中查找最后一个数据域...
  • L是一个带头结点的单链表,函数ListLocateAndDel_L(LinkList L, ElemType x)要求在链表中查找最后一个数据域取值为x的节点并将其删除。例如,原单链表各个节点的数据域依次为1 3 1 4 3 5,则ListLocateAndDel_L(L,3)...
  • L是一个带头结点的单链表,函数ListLocateAndDel_L(LinkList L, ElemType x)要求在链表中查找最后一个数据域取值为x的节点并将其删除。例如,原单链表各个节点的数据域依次为1 3 1 4 3 5,则ListLocateAndDel_L(L,3)...
  • 问题:对于一个没有头指针的单链表,一个指针指向此单链表中间节点(不是第一个,也不是最后一个),将该节点从单链表删除。 思路:获取该节点一个节点,将此节点与下一个节点进行交换,删除其下一个节点...
  • 删除一个无头单链表的非尾节点 //删除一个无头单链表的非尾结点 void DeleteNoHeadNode(ListNode* pos) //pos为要删除的结点 ... //pos为最后一个结点 delete pos; pos = NULL; } else { ListNode* posN
  • struct ListNode{ int val(x); ListNode*next; ListNode(x): val(x),next(NULL){} }; class Solution{ public: ListNode* delecttheaimlastnode(ListNode*phead,int target){ if(ph...
  • 这里依然利用快慢指针办法,让slow指针指向第一个节点,让fast指针和slow间隔N个节点,即指向第N个节点。然后同时移动slow和fast,每次前进一步,直到fast指针到最后一个指针,此时slow指针就是倒数第N个节点,...
  • 题目: ...因为如果想删除和插入一个节点的话,肯定是需要获取前面的一个节点的,但是根据题目所给条件中,我们可以看到我们是不可能获取到前面的一个节点的,所以得另外去想思路了,最后在编...
  • 6-1 删除单链表最后一个与给定值相等结点 (10 分) 本题要求在链表中删除最后一个数据域取值为x的节点。L是一个带头结点单链表,函数ListLocateAndDel_L(LinkList L, ElemType x)要求在链表中查找最后一个...
  • codebloks运行不了 说sh: .....upexpected ( 我找了半天bug 最后发现竟然连helloword程序都执行不了 后来我觉得 会不会是 project命名里 O(1) 然后试着把括号去掉。。居然就行了 后来又建工程加上括号 又是那个错...
  • 一个指针指向此单链表中间一个节点(非第一个节点, 也非最后一个节点)。请将该节点从单链表删除。解答:典型“狸猫换太子”, 若要删除该节点,正常情况下,应该要知道该节点前面节点指针,但是由于单链表...
  • (不是第一个,也不是最后一个),如何将该节点单链表删除。    void DeleteRandomNode(LinkList& pCurrent) {  //Cant Delete the Last One.  assert (pCurrent!=NULL);  LinkList pNext=pC
  • 分析:无头单链表与有头单链表的区别在于找其中的节点不能使用遍历的方法,我们这里定义一个指针cur,让它指向pos的next,然后将cur->data给pos->data,pos->next指向cur->next,最后将cur删除。 void ...
  • 单链表的节点删除新思路 提示:在课上听老师所讲的一种新思路,分享给大家 文章目录单链表的节点删除新思路前言新思路总结 前言 课程上通常的方法就是找到要...提示:该方法可以用于删除单链表的最后一个节点 ...
  • 单链表中从第一个结点出发,顺指针next域逐个往下搜索,直到找到第i个结点为止,否则返回最后一个结点指针域NULL。 按序号查找结点值算法如下: LNode GetElem(LinkList L,int i){ //本算法取出单链表L...
  • 删除单链表中间节点

    2014-11-20 19:23:00
    一个指针指向此链表中间一个节点(不是第一个,也不是最后一个节点),请将该节点从单链表删除---《编程之美》 参考:单链表反转《算法之美》の链表问题の从链表中删除节点 代码待续 。。。。。。 转载于...
  • 在单链表中如果要删除一个节点,需要通过头结点找到该节点的前驱节点,然后让该节点的前驱节点指向它的后继节点,然后free点当前节点就实现了单链表的删除,但是这样的删除需要遍历到当前节点的前驱节点,时间复杂度...
  • 一个指针指向此单链表中间一个节点(非第一个节点, 也非最后一个节点)。请将该节点从单链表删除。解答: 典型“狸猫换太子”, 若要删除该节点,正常情况下,应该要知道该节点前面节点指针,但是由于...
  • 一个指针指向此单链表中间一个节点(非第一个节点, 也非最后一个节点)。请将该节点从单链表删除。 解答: 典型“狸猫换太子”, 若要删除该节点,正常情况下,应该要知道该节点前面节点指针,但是...
  • 创建结构体,结构体中包含数据域INT32 iNum和指针域struct list *Next,根据指针域指示直到最后一个指针域指向空(NULL)。 typedef struct list { INT32 iNum; struct list *Next; }List, *PList; 首先是创建...
  • 一个指针指向此单链表中间一个节点(不是第一个,也不是最后一个节点),请将该节点从单链表删除。 一般链表的删除需要顺着头结点向下找到当前待删节点前驱节点,然后让前驱节点指向后驱节点就行了。这里...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 432
精华内容 172
关键字:

删除单链表的最后一个节点