V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
ads123
V2EX  ›  程序员

尴尬的面试题,没有解决,估计面试官在后台偷笑

  •  1
     
  •   ads123 · 183 天前 · 7632 次点击
    这是一个创建于 183 天前的主题,其中的信息可能已经有所发展或是发生改变。

    给定链表的头指针和一个结点指针,在 O(1)时间删除该结点。不删除头尾结点 typedef struct LNode{ int data; LNode *next; }LNode, *List;

    函数的声明如下: void DeleteNode(ListNode* pListHead, ListNode* pToBeDeleted);

    我没有找出解决办法一直在纠结怎么直接下标索引。结果真是想多了

    50 条回复    2021-04-19 15:54:37 +08:00
    zhongrs232
        1
    zhongrs232   183 天前
    查了一下解决办法,妙啊
    zxCoder
        2
    zxCoder   183 天前
    node.next=node.next.next 这样?
    BBCCBB
        3
    BBCCBB   183 天前
    哈哈, 搜了一下, 值替换..哈哈哈
    Kangst
        4
    Kangst   183 天前 via Android   ❤️ 5
    查了一下,方法是将下一个结点的值赋给当前结点,然后删除下一个结点,就相当于删除了当前节点。简直是妙蛙种子吃了妙脆角进了米奇妙妙屋,妙到家了。
    node.data = node.next.data;
    node.next = node.next.next;
    yucao
        5
    yucao   183 天前
    把 ToBeDeleted.next 节点的内容值复制给 ToBeDeleted 节点,然后删掉 ToBeDeleted.next 节点吧...
    这感觉是纯脑筋急转弯...
    Cu635
        6
    Cu635   183 天前
    @zxCoder
    @Kangst
    @yucao
    那么,原先的 node->next 怎么 free ?
    aijam
        7
    aijam   183 天前   ❤️ 3
    这是很基本的面试题,不会的话大厂肯定没洗
    gstqc
        8
    gstqc   183 天前 via Android
    这种题没意义
    yucao
        9
    yucao   183 天前
    @Cu635
    这有何难?值复制完成后,
    LNode* p = pToBeDeleted.next;
    pToBeDeleted.next = pToBeDeleted.next.next;
    free(p);
    zxCoder
        10
    zxCoder   183 天前
    @Cu635

    var t=node.next;
    node.next=node.next.next;
    free(t);

    这样?


    (free 啥啊 让 GC 自己去 free
    zxCoder
        11
    zxCoder   183 天前
    @zxCoder 不对 写错了
    constexpr
        12
    constexpr   183 天前 via Android
    不遍历的话被删除的结点的父结点的指针如何设置呢?
    疑惑
    zhongrs232
        13
    zhongrs232   183 天前
    想了下,这题应该是被题目坑了,如果函数参数里把头结点去掉,只留一个待删除结点作为参数,我估计大部人都能想到解法。
    constexpr
        14
    constexpr   183 天前 via Android
    @constexpr 如果是分配在连续空间,指针做减法倒是可以取到被删除结点的父结点
    JokerZX
        15
    JokerZX   183 天前
    那他给头结点做啥呀
    xuanbg
        16
    xuanbg   183 天前
    node = node.next
    zhuangzhuang1988
        17
    zhuangzhuang1988   183 天前
    "我们是专业的,再好笑都不会笑,除非忍不住"
    paoqi2048
        18
    paoqi2048   183 天前
    @JokerZX 如果待删节点为末尾节点,还是要从头节点开始遍历
    nnqijiu
        19
    nnqijiu   182 天前   ❤️ 1
    头结点就是没用的信息,算法都玩技巧了
    Knuth
        20
    Knuth   182 天前 via Android
    @paoqi2048 可以判断 node. next,不用遍历
    Rocketer
        21
    Rocketer   182 天前 via iPhone
    好像在《数学之美》里见过,但从来没用到过,因为 leetcode 里类似的题都要求不能改 node 的值
    eephee
        22
    eephee   182 天前 via Android
    @Knuth 不用遍历怎么删除呢?
    FACEB00K
        23
    FACEB00K   182 天前   ❤️ 1
    昨天在 leetcode 上做过,评论还是挺搞笑的 https://leetcode-cn.com/problems/delete-node-in-a-linked-list/
    wheeler
        24
    wheeler   182 天前 via iPhone
    《剑指 offer 》的 13 题。
    yolee599
        25
    yolee599   182 天前 via Android
    @eephee 无需知道前驱节点,直接把要删除的节点替换为下一个节点。next 变成下一个节点的 next,data 变成下一个节点的 data
    smdbh
        26
    smdbh   182 天前
    我想知道原来指向下一个节点的指针,怎么办?
    zmxnv123
        27
    zmxnv123   182 天前 via iPhone
    剑指 offer 至少 dei 刷几遍吧
    xinshoushanglu
        28
    xinshoushanglu   182 天前
    可以,脑筋急转弯哈哈
    raaaaaar
        29
    raaaaaar   182 天前
    表示我们数据结构课上就讲了。。
    felixlong
        30
    felixlong   182 天前
    nngt 。这是脑筋急转弯啊。这不是删除,这是交换。
    securityCoding
        31
    securityCoding   182 天前
    面了三家大厂,算法题全部是中等题 , 回溯+动态规划
    Edcwsyh
        32
    Edcwsyh   182 天前
    @felixlong 这没用交换, 就是单纯的移动覆盖...
    Knuth
        33
    Knuth   182 天前 via Android
    @eephee node. next 为空,直接把当前节点置空不就是删除了
    Kangst
        34
    Kangst   182 天前
    @Cu635 针对这道题而言,用 c/c++好像不能 free,可以参考 leetcode 237 题里面 c++的一个题解,讨论了这个问题。
    另外,力扣官网的剑指 Offer 18 也是这个题,题目说明里写了如果使用 c/c++不需要考虑 delete 或 free 结点;我觉得这题就当个脑筋急转弯,能得到结果就行了,本身题目就不好。
    MiniGhost
        35
    MiniGhost   182 天前
    面试考脑筋急转弯就没意思了啊,这种题不应该出现在面试中
    eephee
        36
    eephee   182 天前 via Android
    @yolee599 关键是如果要删除的节点是最后一个节点,就没办法了
    eephee
        37
    eephee   182 天前 via Android
    @Knuth 怎么把当前节点置空啊,赋值为 NULL 没法置空,只能将指针变量指向 NULL,没法改变原有节点
    eephee
        38
    eephee   182 天前 via Android
    @JokerZX 可能这个函数最后要返回头节点,所以参数也带了个头节点
    yolee599
        39
    yolee599   182 天前 via Android
    @eephee 题目是不删除头尾节点,由于这个是单向链表,头节点直接由传入的参数得知,而尾节点则可以通过 p->next == NULL 得知
    eephee
        40
    eephee   182 天前
    @yolee599 哦哦原来是不删除头尾节点,没看题误解了
    Vegetable
        41
    Vegetable   182 天前
    leetcode 原题,当初做到这道题的时候就觉得这种题很恶心,内存里的地址又没变就挺反套路的
    Vegetable
        42
    Vegetable   182 天前
    面试官如果笑得出来,太 low 了,说实话选这个题目当面试题,配得上一句脏话
    csfreshman
        43
    csfreshman   182 天前
    leetcode 有原题,也不难想呀,面试的时候可以抛出来这个方法,我面试也遇到过,后面刷 leetcode 发现是原题。
    weyou
        44
    weyou   182 天前 via Android   ❤️ 1
    删除节点的含义就是将指定节点的数据结构从链表中脱钩,而从链表中删除某个值,这题的解法不太地道,纯属脑筋急转弯
    dingyaguang117
        45
    dingyaguang117   182 天前
    2012 年百度校招一道题 = =
    jiangshanmeta
        46
    jiangshanmeta   182 天前
    leetcode
    属于脑筋急转弯类型
    Cu635
        47
    Cu635   181 天前
    @yucao
    @zxCoder
    确实犯二了……
    dingwen07
        48
    dingwen07   181 天前 via iPhone
    这事我刚在一个作业里干过
    THESDZ
        49
    THESDZ   181 天前
    链表的定义知道了,应该会知道怎么搞吧= =
    lakehylia
        50
    lakehylia   180 天前
    单纯为了面试的题,如果数据不是基本类型,那赋值又是一个带坑的。。。
    关于   ·   帮助文档   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   2016 人在线   最高记录 5497   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 24ms · UTC 04:00 · PVG 12:00 · LAX 21:00 · JFK 00:00
    ♥ Do have faith in what you're doing.