V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
• 请不要在回答技术问题时复制粘贴 AI 生成的内容
shenwu35
V2EX  ›  程序员

工作 8 年手写不出反转链表是不是进不了 bat 了?

  •  
  •   shenwu35 · 2021-01-04 21:23:36 +08:00 · 10410 次点击
    这是一个创建于 1451 天前的主题,其中的信息可能已经有所发展或是发生改变。

    心烦意乱图上画半天无法代码写出,跟自己较劲不看答案, 硬写都快抑郁了,看答案下次还是忘记,所以硬肝,这很痛苦,救命。

    现在还没肝出来,怎么宽慰自己?

    第 1 条附言  ·  2021-01-05 00:35:52 +08:00
    感谢各位同行善意鼓励,也感谢各位劝退转行编码能力不行循环会就该会的建议。

    12 点半了,没肝出来,困了,打工人打工魂,永不为奴。

    本帖会持续更新直到肝出来为止。


    洗洗睡,看着媳妇孩子熟睡的样子,一道破题影响不了我,明日再战。

    晚安,命要紧,
    72 条回复    2021-01-06 22:45:55 +08:00
    kyokuheishin
        1
    kyokuheishin  
       2021-01-04 21:27:21 +08:00 via iPhone
    没事刷刷 leetcode,多几次相关题就记住了
    yhxx
        2
    yhxx  
       2021-01-04 21:30:02 +08:00
    别慌,我也写不出来,还是混进来了
    luckyrayyy
        3
    luckyrayyy  
       2021-01-04 21:30:15 +08:00
    熟练度问题吧,我做那个正则表达式的也是,错了不知道多少次,每次做完过几天也错,最终反正是错的越来越少,想起来的越来越快,加油!![image]( )
    heyjei
        4
    heyjei  
       2021-01-04 21:33:01 +08:00   ❤️ 2
    不要想着一步就写出最优的解法,先按我们思维最自然的想法写出“最笨”的解法,然后再一步步优化。💪💪💪💪
    shenwu35
        5
    shenwu35  
    OP
       2021-01-04 21:34:20 +08:00   ❤️ 1
    去年看答案,写出来了,今年再写又不记得了,都要怀疑人生了,谢谢各位同行鼓励,抽根烟继续肝,为了证明自己还能战,8 年老兵成这样,心酸。
    anguiao
        6
    anguiao  
       2021-01-04 21:38:04 +08:00 via Android   ❤️ 1
    毕业越久,写不出来的概率越大。前段时间把大学的数据结构作业翻出来了,很难相信是我自己写出来的😂
    jmc891205
        7
    jmc891205  
       2021-01-04 21:46:21 +08:00   ❤️ 1
    大多数 easy 题 就算没刷过 也应该能很快写出一版才对。。。只是有些 corner case 考虑不到的话可以理解
    DoctorCat
        8
    DoctorCat  
       2021-01-04 22:01:05 +08:00
    抱着学习的心态去刷就好了。
    durban126
        9
    durban126  
       2021-01-04 22:06:17 +08:00
    说实话 这种算法的东西 用的时候看下就可以了
    另外这种算法不是会一次以后都会记住的,记性好的除外
    像我都是找个小本子记下来
    下次用的时候拿出来直接用了
    都 21 世纪了,网上一搜一箩筐的代码
    yzbythesea
        10
    yzbythesea  
       2021-01-04 22:09:54 +08:00
    基础还是有点儿差。反转链表等于解一元二次方程的难度吧。
    learningman
        11
    learningman  
       2021-01-04 22:21:38 +08:00   ❤️ 2
    照我的认知,知道链表是啥应该就会写反转链表吧。。。
    carlclone
        12
    carlclone  
       2021-01-04 23:33:03 +08:00 via Android
    编码能力不过关吧,这题面向测试用例编程也早写出来了
    whimsySun
        13
    whimsySun  
       2021-01-05 00:00:49 +08:00
    别说 bat 了,建议早日换行吧
    cmdOptionKana
        14
    cmdOptionKana  
       2021-01-05 00:19:03 +08:00 via Android
    看了答案还忘记?这个理解了不容易忘记的啊...
    Caballarii
        15
    Caballarii  
       2021-01-05 00:23:09 +08:00
    会循环就会写反转链表了
    shenwu35
        16
    shenwu35  
    OP
       2021-01-05 00:37:17 +08:00
    @cmdOptionKana 去年看了答案,写完画了下,今天再写死活画不出来图了,哎,看来还是没深刻理解。
    shenwu35
        17
    shenwu35  
    OP
       2021-01-05 00:40:08 +08:00
    @cmdOptionKana 然后自己画了图代码运行后还是不达预期,哎,我承认我数据结构算法基础差,没花精力去刷题去理解去系统化思考。
    ruokw
        18
    ruokw  
       2021-01-05 00:42:53 +08:00 via Android
    说难听点 你这就废了。但是我想说的是,没必要硬要纠结 xxx 题不会,工作八年,项目经验才是你资本,讲究的就是扬长避短
    stdout
        19
    stdout  
       2021-01-05 01:13:29 +08:00   ❤️ 4
    君子生非异也,善假于物也。会写 100 种排序方法是很牛逼,但大部分场景真不需要。
    xupefei
        20
    xupefei  
       2021-01-05 01:17:33 +08:00 via iPhone
    虽然工作中用不到,但现实就是如此。想进大厂,不管几年经验都要先来几道算法题。
    面试流程已经是标准化考试了。
    irytu
        21
    irytu  
       2021-01-05 01:19:54 +08:00 via iPhone   ❤️ 5
    其实还是写少了 而且这玩意跟你工作多少年还真没多大关系 试问几个公司没事业务让你操作链表 二叉树这类数据结构的 就算有 你能年年有机会这么搞吗?

    写代码,量累到一定地步了,自然会有质变,至少熟练度肯定也有改善的,反正就是写写写,让比你厉害的人给你 review 提建议

    那些劝退的 其他不说 就想问你们生来什么都会不用学 啥都不准备 个个都能手撕大厂面试官? 有的人准备在前 有的人准备在后 真不知道有啥好劝的

    楼主要是闲着可以整点副业做做 写写代码 你每天写一点 时间久了就好了 面试准备一点套路也行 推荐一本书 crack the coding interviews,前面几章别跳过,leetcode 按类别刷题,复习到哪里就写几道相关的题,我有时间下班就写几道,没时间或者累了就休息,没必要搞很累
    dartabe
        22
    dartabe  
       2021-01-05 01:58:32 +08:00
    链表题就是要多做几道就熟了 有套路的
    iConnect
        23
    iConnect  
       2021-01-05 06:25:12 +08:00 via Android
    你现在回去做高考数理化试卷,也不如原来分高。这是需要训练保证的,不表示比以前更蠢了
    Nerv
        24
    Nerv  
       2021-01-05 08:08:59 +08:00 via Android
    递归思想的写法比较好理解和记忆。有时候没有思路是因为心态问题,不要给自己太大压力。
    djoiwhud
        25
    djoiwhud  
       2021-01-05 08:50:09 +08:00 via Android   ❤️ 2
    工作 9 年多,让我面试写链表反转是不可能的。连快排都搞不定了,只会写冒泡排序。

    都这把年纪了,为啥要执著于进 bat 呢?这行业赚钱的人从来不是以技术为评估标准排序的。要淡化码农的印记。
    serverABCD
        26
    serverABCD  
       2021-01-05 08:59:06 +08:00
    啊这,,虽然业务代码和 leetcode 没什么关系,但是反转链表,反转二叉树,回朔,深广度优先遍历不应该信手拈来么。加油
    Suddoo
        27
    Suddoo  
       2021-01-05 09:10:11 +08:00
    这个我只能写出递归版本,迭代版本要复习一下才能写出来
    jcto
        28
    jcto  
       2021-01-05 09:13:57 +08:00
    请了解钻牛角尖。
    yangxin0
        29
    yangxin0  
       2021-01-05 09:14:21 +08:00 via iPhone
    这种基础算法和数据结构最好能随意写,链表、栈、二叉树、排序,另外别把 bat 抬得太高里面有牛人但是大部分还是 crud
    lewis89
        30
    lewis89  
       2021-01-05 09:15:54 +08:00


    https://leetcode-cn.com/problems/minimum-window-substring/

    错了很正常,我这看完题解 写出代码 还 debug 了 差不多 1 个小时,

    多写测试用例,我一般都是在 IDE 里面写的,有 test case 多断言 比较容易找出问题

    其实我一直都反对白板编程的,大部分人脑短期记忆力并不好,记不住大量的上下文,

    尤其是推演算法正确性 特别是很多题涉及到+1 -1 的地方 更容易出错,需要记住很多中间状态以及上下文才能推演出一个小的 test case 的正确性,除非你模板背得特别好,还刚好碰上那道题,那当我没说。

    特别是平时根本没怎么写过的套路代码的更容易在这方面犯糊涂,

    即使真实的面试 我也建议 先把 test case 边际条件先写在一边,然后复盘代码的时候照着 test case 往下看

    平时业务代码过于复杂的话,我也会写好简易的单元测试,这种脚手架的代码 可以帮助定位问题

    另外推荐一下算法小抄那本书,用作面试是绝对够了。
    gongshishao126
        31
    gongshishao126  
       2021-01-05 09:17:59 +08:00
    @luckyrayyy 冒昧的问一下,正则也要会手写吗~~~我用的时候一般都是百度,比如简单的校验手机号、身份证号等等,是不是要恶补掌握一下
    hbhswj
        32
    hbhswj  
       2021-01-05 09:20:15 +08:00   ❤️ 1
    看了一些评论,实在忍不住说两句,😂某些大佬不知道写代码强不强,反正敲键盘挺 6 。

    楼主加油,力扣小刷怡情即可,不是搞算法的,没必要死磕,看答案自己写看答案自己写,重复直到有个概念即可。

    还有一些评论里说转行的、劝退的、酸的,不用理会,现实中的他们可能别说题了,最起码的毅力都没有,才会来网络上找找存在感,吹吹牛 b 。不是说话难听,毕竟网络上都是人均 985,刚下飞机~
    qwerthhusn
        33
    qwerthhusn  
       2021-01-05 09:27:24 +08:00
    同工作 8 年,花了 10 分钟写出来了,还跑了 main 修改了两把才成功。

    Node reverse(Node head) {
    Node priv = head;
    Node node = head.getSetNext(null);
    while (node != null) {
    Node originalNext = node.getSetNext(priv);
    priv = node;
    node = originalNext;
    }

    return priv;
    }
    lewis89
        34
    lewis89  
       2021-01-05 09:30:36 +08:00
    其实算法面试主要考察就两方面的能力,而这两方面的能力大多在程序员的现实工作中是几乎不怎么需要的。

    1. 长期记忆能力,你需要背诵算法题的套路模板,并加以理解记忆,以便于在算法面试中快速搜索到解题思路,这大概是程序员最不需要的技能,因为本科教科书上大量的算法都在网络上有各种千奇百怪的解法与解读,而程序员在工作中很大一个工作任务就是阅读理解他人的文档,使用前人的工作成果或者在前人的基础上加以改造,现实中也不会有面试这样紧迫的时间以及几乎没什么工具辅助的情况下要求你快速解题,而且现实中我们大多记住一些算法的复杂度以及这个算法能解决的问题即可,待需要的时候去查找即可,例如我根本记不住拓扑排序算法以及模板,但不妨碍我用它来解决有向图中存在环的问题,因为需要的时候,我仓库里面有大量的资料,随时可以整理出来用于解决问题。

    2.短期记忆能力,你需要记住算法中大量中间上下文,以便通过几个简易的 test case 验证出算法的正确性,而且很多题需要好几个 test case 才能验证代码的正确性,这对我这种短期记忆力不好的人真的是一个折磨,因为我在工作中验证复杂代码正确性的时候,大多都是借助机器的栈幁跟 debug 来验证,而且 test case 都是手写好,机器执行的,而不是人脑执行的,我人脑执行 test case 的时候 即使借助纸板记录 也还是经常掉链子,这也是我做算法题目前 比较慢的原因,当然随着做得多了,短期记忆力会提上来。
    luckyrayyy
        35
    luckyrayyy  
       2021-01-05 10:25:17 +08:00
    @gongshishao126 啊,不是,这个是 leetcode 上的一道题,实现一个非常简单的正则表达式匹配,只有.*两种特殊字符和普通字母。
    hejw19970413
        36
    hejw19970413  
       2021-01-05 10:44:08 +08:00
    一遍不行写两遍 两遍不行写 3 遍 , 就刚开学英语一样,我记得第一个单词就是苹果 apple,一天到晚就是 a p p l e 这辈子都肯定不会忘的, 还是得多练。 就比如说你这道题 。 其实就基础的交换问题。只不过就是得先记录下次我要和谁进行交换。
    zypy333
        37
    zypy333  
       2021-01-05 10:46:21 +08:00
    冒昧问下你肝是为了证明自己还行,还是想进 bat
    raaaaaar
        38
    raaaaaar  
       2021-01-05 10:53:22 +08:00 via Android   ❤️ 1
    无她,唯手熟耳
    todd7zhang
        39
    todd7zhang  
       2021-01-05 10:59:56 +08:00
    筛选链表的题, 从简单一路刷一下去,手熟就秒出
    Suddoo
        40
    Suddoo  
       2021-01-05 11:08:18 +08:00
    @djoiwhud 是的,有时候技术并不是最重要的,技术一般混得好的大有人在
    mxT52CRuqR6o5
        41
    mxT52CRuqR6o5  
       2021-01-05 11:10:48 +08:00
    得看你的写不出是怎么个写不出
    hantsy
        42
    hantsy  
       2021-01-05 11:16:20 +08:00
    早不记得了。

    那是课本上的,早还给老师了。
    onesec
        43
    onesec  
       2021-01-05 11:49:05 +08:00
    楼主加油,最近我也在刷题,多准备一些;现在进很多厂也要考算法题,不一定是 BAT ;
    自己的思路是先写出“最笨”的解法,然后再优化;如果想不出也不死嗑, 放轻松明天再写;
    afewok
        44
    afewok  
       2021-01-05 11:50:41 +08:00
    说起来,去年面头条,给定的算法是掐头去尾,中间链上反转。半小时我也没写出来。
    后面刷了几天 leetcode,楼主说的这种单纯全量反转,加个虚拟头节点,简直分分钟的事。
    ```golang

    type ListNode struct {
    Val int
    Next *ListNode
    }

    func reversal(head *ListNode) *ListNode {
    dummy := &ListNode{-1, nil}
    p := dummy
    for head != nil {
    p, dummy.Next = dummy.Next, head
    head, dummy.Next.Next = dummy.Next.Next, p
    }
    return dummy.Next
    }
    ```
    yedan1206
        45
    yedan1206  
       2021-01-05 11:56:01 +08:00
    你们刷 leetcode 是直接在网页里面写代码,还是先在 ide 写好后运行没问题了,再复制粘贴进去?
    Suddoo
        46
    Suddoo  
       2021-01-05 12:17:42 +08:00
    @stdout 主要是内卷严重吧,以后还可能考微积分什么的
    tikazyq
        47
    tikazyq  
       2021-01-05 13:35:20 +08:00
    写得出来照样进去 996 搬砖
    PopRain
        48
    PopRain  
       2021-01-05 13:47:06 +08:00
    反转链表都写不出来,快 50 岁的程序员认为楼主不适合做编程,这个大概是初学者的题目吧
    bjjvvv
        49
    bjjvvv  
       2021-01-05 14:03:30 +08:00
    刷了 200 多题,做这道题还是没有一遍过
    花了不到 10 分钟吧
    易错点就是反转的时候要先保存到临时变量,和反转二叉树一样
    class Solution {
    public ListNode reverseList(ListNode head) {
    if (head == null || head.next == null) {
    return head;
    }

    ListNode prev = null, curr = head;
    while (curr != null) {
    ListNode next = curr.next;
    curr.next = prev;
    prev = curr;
    curr = next;
    }

    return prev;
    }
    }
    wr516516
        50
    wr516516  
       2021-01-05 17:32:01 +08:00
    加油,奥利给
    zzzzzzggggggg
        51
    zzzzzzggggggg  
       2021-01-05 17:46:43 +08:00
    这说明你之前就没理解过,如果理解了现在忘了,看了答案就能想起来;
    人就别勉强自己了,干点自己喜欢干的吧,年轻的时候就没搞懂,现在怕是更没戏
    456789
        52
    456789  
       2021-01-05 17:51:21 +08:00
    加油加油 我也要加油
    Samuelcc
        53
    Samuelcc  
       2021-01-05 17:58:48 +08:00 via Android
    说实话,一些最基本的题目例如反转链表应该是只要了解这种数据结构就能写出来才对。写不出来确实不应该,得练练了。
    qwer666df
        54
    qwer666df  
       2021-01-05 18:07:59 +08:00
    @luckyrayyy #3 这个是啥平台啊老哥
    luckyrayyy
        55
    luckyrayyy  
       2021-01-05 18:15:17 +08:00
    @qwer666df leetcode
    coolesting
        56
    coolesting  
       2021-01-05 18:38:43 +08:00 via Android
    不写低层的,基本用不上算法。写不出也正常。
    lzlee
        57
    lzlee  
       2021-01-05 18:39:01 +08:00
    熟练度问题...

    这种考试, 本质上只是问你直到不知道,
    而不会问你, 这玩意你是怎么发现的, 为了解决什么问题发现的, 最后效果怎么样
    就算你花十天硬背下来了, 你不说也没人知道你怎么记下来的

    真的看了这个, 就能进 bat 了?
    想想, 你看会了就能进去, 你这成长速度不是很快吗?

    扯远了, 老哥加油
    Claar
        58
    Claar  
       2021-01-05 19:05:38 +08:00 via iPhone
    个人意见:虽然多数人多数情况下不需要用到算法,但是反转链表这种问题简单的令人发指,写不出来确实有问题,算法题基本可以理解为数学和 coding 的结合,链表基本不要求数学水平,写不出来可能是编码能力低下,建议多练习,一般人很难练不会
    VinsonGuo
        59
    VinsonGuo  
       2021-01-05 19:15:04 +08:00 via Android
    0 年工作经验闭着眼睛写,十年工作经验的可能连冒泡都写不出来🤣
    Claar
        60
    Claar  
       2021-01-05 19:21:42 +08:00 via iPhone
    上厕所时间随便写伪代码,反转链表是吧,原理很简单,需要三个点,pre 原当前点的前一个点,cur,next
    先定一个 pre=node()
    cur=root
    next=cur.next
    三个点初始化完成


    当前点的 next 改指向前一点 cur.next=pre
    要考虑 next 是否为空,空就结束了,不空继续
    三点整体推前,注意顺序,因为有些点一旦改名就找不到了,比如此时的 cur,还有某些点不需要照顾如 pre,所以顺序来了,
    pre=cur,cur=next,next=next

    直接重复上一段操作,for 起来
    埋了一个 bug,不提示
    回去实现看看对不对
    Claar
        61
    Claar  
       2021-01-05 20:08:06 +08:00
    class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
    if not head:
    return head
    pre = None
    cur = head
    next = cur.next


    while 1:
    cur.next = pre
    if not next:
    return cur
    pre = cur
    cur = next
    next = cur.next


    由于太久没写了,没了刷题是注意输入为空的情况所以刚才没有提到 head 为空的情况,结果是两次提交
    之前提的 bug 是我上面初始化 pre 是一个空结构,那是要最后剔除掉的,这里直接用 None 就结束了,不需要剔除,当然 pre 初始化为空结构在链表题例有很多好处,所以我习惯性的会初始化为空结构
    这种题目是入门中的入门,数学难度和编码难度都完全没有,不可能学不会,记得多动脑,先理解再实现,像我前面提到的按着思路写,一点难度都没有好吧
    楼主加油啊,这种东西根本没难度的,如果觉得想出思路很难可以加我,到时候进了 bat 别忘了带带小弟就行哈哈哈哈哈
    wanglufei
        62
    wanglufei  
       2021-01-05 22:06:20 +08:00 via Android
    画图理解一下吧
    pythonee
        63
    pythonee  
       2021-01-05 22:29:47 +08:00
    我已经不记得反转链表的概念了,但还在大厂
    akakidz
        64
    akakidz  
       2021-01-05 22:33:18 +08:00 via Android
    写五遍之后...闭着眼都能写了...我是菜鸡一个,但是我觉得这种题目不会写没必要硬刚,你还能自己空手造出一个原子弹吗
    Claar
        65
    Claar  
       2021-01-05 23:42:20 +08:00
    @pythonee 记不记得不重要好吧,这种入门难度的题目,要练也很好练,我觉得哪怕是不知道问题都不大,世界那么大没必要什么都懂,但是理解不了或理解了写不出来,问题就很大了
    10bkill1p
        66
    10bkill1p  
       2021-01-06 09:16:17 +08:00
    我也不会😁
    guonaihong
        67
    guonaihong  
       2021-01-06 09:39:51 +08:00
    翻转链表,重新插入一遍就是反的。会插入逻辑就行。
    zoyua
        68
    zoyua  
       2021-01-06 10:10:45 +08:00
    记不住很正常,把递归和迭代的题解多写几遍就记住了
    wangbenjun5
        69
    wangbenjun5  
       2021-01-06 10:33:47 +08:00
    不会真的有人以为只要是程序员就一定得会算法吧?

    IT 行业分类很大很广,自以为只有部分涉及底层架构领域开发需要熟知各种算法,大部分岗位都是花式 CRUD 业务相关的开发,要算法有什么用,了解算法是一方面,能够无 bug 手写又是另一个维度。

    先不说反转链表,就说链表这个数据结构,真正开发的时候哪个不是直接现成的库,还会自己手动写???

    至于面试,我觉得不是所有岗位都会死考算法,BAT 里面菜逼也一堆,打酱油的岗位也很多,不是个个都是大神,除非是算法岗
    Still4
        70
    Still4  
       2021-01-06 11:19:53 +08:00
    ```
    class Solution {
    public ListNode reverseList(ListNode head) {
    ListNode newHead = null;
    ListNode current = head;
    while (current != null) {
    // ListNode temp = new ListNode(current.val);
    // if (newHead != null) {
    // temp.next = newHead;
    // }
    // newHead = temp;
    // current = current.next;
    ListNode next = current.next;
    current.next = newHead;
    newHead = current;
    current = next;
    }
    return newHead;
    }
    }
    ```
    注掉的部分是我自己理解的过程,生成新的链表,每个节点生成新的对象,注释外的的是前面有人提的,直接操作原始数据,其实就是想清楚过程,平时多思考吧
    hehe12980
        71
    hehe12980  
       2021-01-06 15:02:43 +08:00
    说真的,反转链表很简单把 最简单的方法就是遍历 一次 把节点的数拿出来 放到栈里 再遍历 构建一个链表,你要说递归或者指针转移的方式想不到 可以理解
    shenwu35
        72
    shenwu35  
    OP
       2021-01-06 22:45:55 +08:00
    经过实战,头插法,增加虚拟头节点,非递归的方式写好了。如图: https://prnt.sc/whka1v

    对于递归版本还在继续肝。
    至于为何肝,是为了证明自己理论多年学过复习后还是能实际代码跑成功的,当然也是 冲这个目标准备,严要求才可能得到中等结果,也是给自己提提气,不屈服吧。

    评论区我翻完了,8 年的我进 bat 与刚毕业 985 学历新人也没优势了,除非项目很亮点,普本学历也没优势,我清楚自己的定位。
    不过另外朋友说项目经验才是我的重点,扬长避短,这个非常赞同,我会深挖项目经验。
    还有个朋友说 牛角尖,谢谢您的提醒,我只为了这题来提气不会阻塞,我知道更重要的扬长避短和时间的宝贵和紧迫性。
    还有个大哥说 8 年了,要摆脱码农印记,多在商业需求上思考也是非常赞同。当然对于毕业前 5 年,技术还是第一位修炼。
    最后,我看完评论区各位的鼓励动力很足,也没想过放弃这个破题。再次谢谢技术单纯的同行们,各位也要好心情保护身体,改变世界。希望明早上班刷到本回复的同行开启美好一天,return .
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1735 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 25ms · UTC 16:37 · PVG 00:37 · LAX 08:37 · JFK 11:37
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.