【真实面试】找错误：面试某大厂手写链表题，找找他错在哪里了？

这是一个读者面试某大厂时，在线写删除链表倒数第 n 个节点的算法题，不过我说过，链表题很容易出错，他也是犯了致命错误。

现在考验一下大家，大家看看他的代码错在哪里？
打卡：找出他哪里错了

参考答案：没有考虑空指针问题，如果删除的是第一个节点，也就是头节点，那么会出现异常。因为在第一个 while循环之后，fast 为 null，这样就无法进去第二个while循环，此时 pre 就一直为 null，最后调用 pre.next 就会出问题。

shuaidi

更新于 3 年前 251 24

共以下 24 个回答

黎明之前普通 2023年8月28日上午1:48

没有考虑空指针问题，如果删除的是第一个节点，也就是头节点，那么会出现异常

0 赞同 0 条回复

登录以回复
我一定要坚持打卡普通 2023年8月27日上午8:47
链表的操作，需要设定自己的模板

【真实面试】找错误：面试某大厂手写链表题，找找他错在哪里了？-跟着帅地玩转校招，拿捏大厂offerPlayOffer

在看第二天打卡的第4个题目的时候，大厂面试官给出的是删除倒数第n个节点，自己按照视频里边他的思路走下来发现就是自己前两天刚做的那个题目，他的思路是对的，只不过是把删除节点和找倒数第n个节点结合在一起，自己就没有把这个综合题目给全面细致的写出来，问题如下

没有考虑到节点为空的情况，也就是head为空

没有全面的想到n的范围，n可能大于链表长度也可能等于链表长度（删除头结点），只考虑了n小于链表长度（删除链表内部的数据，也就是跟着视频走了下来，没自己独立思考）

看到题目没有想到解题目的方法，没有完成自己对于链表题目的知识体系，例如拿到链表题目之后，先设定好空的头结点，用带头结点的链表进行操作；然后思考怎样去实现对应的算法，暴力法，双指针法，递归解决，栈和队列，基本的链表操作等等；特殊的情况例如范围越界，head为空等特殊情况处理

改进如下

设定自己的模板，看了下代码随想录上的内容，有直接对应删除倒数第n个节点的题目 代码随想录 (programmercarl.com)](https://programmercarl.com/0019.删除链表的倒数第N个节点.html#算法公开课) 忘了之前跟着做过了都，也没有自己手敲，所以基本等于没看

整理下自己对于链表题目的套路，设定头结点，以防出现没考虑到的情况，【头指针为空，单独处理第一个头结点】

自己对于题目还是不太熟练，只是单纯自己做了一遍，应该更多的思考总结

【视频里边那个哥们就是拿到题目就先自己做起来了，没有考虑到自己应该怎么去想？这个题目是哪些题的变体？怎样对边界值做处理？面试官要怎样讨论边界值等等问题……然后再自己去做】反转就是，大家看到一道面试题，切完不能噼里啪啦做，而是要讨论好边界条件，再去做，否则你就要自己判断所有边界，麻烦的很。

面试官也是很希望你能和他讨论分析的
0 赞同 0 条回复

登录以回复
Di questa storia sempre a lie to 普通 2023年8月24日上午12:31

1、没有考虑到删除头节点的情况，
2、n大于链表长度的情况也未考虑

0 赞同 0 条回复

登录以回复
谁仁普通 2023年8月21日上午10:18

没考虑到头节点，以及快指针应该是n-1为fast才行，不能再往下next

0 赞同 0 条回复

登录以回复
Delete隐身普通 2023年8月18日下午10:08

没有考虑到当n的值等于或者大于链表长度的情况：
如果n的长度等于链表长度，此时要删除的节点是第一个节点，也就是说pre会为空，此时应该是head = head.next，并返回head；
如果n的长度大于链表长度此时不应该执行删除节点操作

0 赞同 0 条回复

登录以回复
💮黧大王.exe 普通 2023年8月16日下午7:33

若删除的是头节点，则第一个循环后fast为NULL，pre为NULL，无法进入第二个循环，pre值为NULL，无法调用pre->next。

0 赞同 0 条回复

登录以回复
一个人的风海吹了两遍普通 2023年8月16日下午4:53

没有考虑n超过链表长度时的情况
以及删除只有头结点的情况

0 赞同 0 条回复

登录以回复
Miracle· 普通 2023年8月16日下午4:51

删除节点时没有考虑到删除头节点的情况

0 赞同 0 条回复

登录以回复
Sheng 永久会员 2023年8月16日上午10:37

删除节点时，将头节点中部节点末尾节点的情况都分析分析。一般中部节点与尾节点处理是相同的。头节点需要特殊处理。

0 赞同 0 条回复

登录以回复
QQiing 普通 2023年8月15日下午5:23

当删除的是头节点的时候，会出现问题。pre为nullptr，pre->next复制就会出现问题。

0 赞同 0 条回复

登录以回复
小肸永久会员 2023年8月15日上午10:41

没有考虑头节点问题。一般解决链表问题时要注意特殊情况就是头节点，可以考虑建立一个虚拟头节点解决。或者自己额外写代码对头节点进行特殊处理。另外就是一般需要注意空指针问题，这个就考验代码能力了。

0 赞同 0 条回复

登录以回复

行动派小彩笔普通 2023年8月15日上午10:02

/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 *  ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @param n int整型 
     * @return ListNode类
     */
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        // write code here
        if(!head) return nullptr;
        ListNode* newHead = new ListNode(-1);
        newHead->next = head;
        ListNode* pre = newHead,* cur = head,*deleteNode = head;
        for(int i=0;i<n;++i)
        {
            if(cur) cur = cur->next;
            else return nullptr;
        }
        while(cur)
        {
            cur = cur->next;
            pre = pre->next;
            deleteNode = deleteNode->next;
        }
        pre->next = deleteNode->next;

        return newHead->next;
    }
};

0 赞同 0 条回复

sincere 普通 2023年8月14日下午10:07

快指针 fast 先走 n 步，然后快慢指针同时往后走，走到 fast 为 null 时 slow 就是倒数第 n 个节点
视频存在的问题是 fast 和 slow 都初始化为 head 头节点，假设要删除的就是头节点，那么第一个 while 时 fast 就已经为 null 了，无法进入第二个 while，出现 NPE。
1、可以在第二个 while 后面加个判断 if(slow.next ==head){ head = head.next} else {正常的删除}；2、更好的方式是添加虚拟头节点 dummy，初始化时都指向 dummy，删除不需要特殊判断，最后返回 dummy.next 即可

0 赞同 0 条回复

登录以回复
逸兴遄飞普通 2023年8月14日下午2:34

要注意到在循环时快指针会比慢指针先进入null，因此他所写的代码在示例二的情况下fast.next直接为null，并且赋值回fast中。这就会导致对第二个while的判断为不进入循环，那么slow的值不会添加到pre中，在后面pre->next=slow->next语句中的pre仍然是初始设置的null，不存在next，赋值报错。

0 赞同 0 条回复

登录以回复
晓宇普通 2023年8月14日上午11:19

所有的删除题目都很容易把人绕晕，因为删除题目涉及到.next.next，所以一般最少要为两个节点，head None or head.next None，无节点或者1个节点的时候都应当直接删除。然后在考虑normal的情况

0 赞同 0 条回复

登录以回复
Marc 普通 2023年8月14日上午2:45

只有一个节点情况未考虑

0 赞同 0 条回复

登录以回复
mpweixin用户普通 2023年8月14日上午2:38

在第二個示例時由於只有一個節點, 在第一個循環時fast會指向 NULL 因此就不會進入第二個節點, 這時的pre還是NULL 如果呼叫pre->next=slow->next就會報錯

0 赞同 0 条回复

登录以回复
mpweixin用户普通 2023年8月14日上午12:42

没考虑头节点被删除

0 赞同 0 条回复

登录以回复
别扒拉我普通 2023年8月13日下午11:56

边界没处理好吧

0 赞同 0 条回复

登录以回复
天亮说晚安普通 2023年8月13日下午11:31

边界未处理

0 赞同 0 条回复

登录以回复
Jou Siankwa 普通 2023年8月13日下午11:19

如果只有head节点，pre为空没有经过第二个while循环，导致pre.next报错

0 赞同 0 条回复

登录以回复
木子有点甜🍒 普通 2023年8月13日下午10:33

在n递减控制while循环时，如果正好要获取的是倒数第一个节点，fast最后会指向空。不需要以n来控制fast指针的步伐，只要保证slow指针是比fast慢n步出发即可，最终的遍历结束条件应该是fast指向空

0 赞同 0 条回复

登录以回复
c 普通 2023年8月13日下午4:04

只有一个节点时，进行最后一步时pre为空指针，pre.next会报错

0 赞同 0 条回复

登录以回复
mpweixin用户永久会员 2023年8月13日下午3:51

示例2会报错；由于链表只有一个元素，fast在第一个循环中就为null了，这导致不会执行第二个循环。进而导致pre依旧为空指针，从而pre.next = slow.next 会报错

0 赞同 0 条回复

登录以回复