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

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

  •  1
     
  •   ads123 · 2021-04-17 10:22:39 +08:00 · 8544 次点击
    这是一个创建于 1076 天前的主题,其中的信息可能已经有所发展或是发生改变。

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

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

    这样?


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