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

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

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

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

shuaidi

更新于 3 年前 223 35

共以下 35 个回答

莫～慢～待普通 2024年3月9日下午8:07

没有考虑k为n的特殊情况,会出现空指针

0 赞同 0 条回复

登录以回复

e=mc² 普通 2024年3月6日下午10:06

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if (head == null) {
            return null;
        }
        ListNode slow = head, fast = head;
        for (int i = 0; i < n; i++) {
            fast = fast.next;
        }
        // 判断边界 如果n等于链表的size则无法进入下面的while循环
        if (fast == null) {
            return head.next;
        } else {
            while (fast.next != null) {
                fast = fast.next;
                slow = slow.next;
            }
            slow.next = slow.next.next;
            return head;
        }
    }
}

0 赞同 0 条回复

Yeah~ 普通 2024年3月6日下午4:13

删除第一个节点时，fast走到nullptr，不进循环，pre未被赋值还是nullptr，为pre->next赋值时报错。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        if(head == nullptr|| head->next ==nullptr) return nullptr;

        ListNode* pre = head, * post = head;
        while(n--){
            post = post->next;
        }
        if(post == nullptr){
            return pre->next;
        }
        ListNode* slow = nullptr;
        while(post!=nullptr){
            slow = pre;
            post = post->next;
            pre = pre->next;
        }
        slow->next = pre->next;
        return head;

    }
};
//只需在post指针先走完后判断是否为空，若为空，则是删除第一个节点，直接返回head->next即可

0 赞同 0 条回复

30tcq 普通 2024年3月6日下午3:27

没有考虑k为n的特殊情况

0 赞同 0 条回复

登录以回复
YOLO 普通 2024年3月6日上午11:39

如果删除的是第一个节点，会出现空指针情况，fast指针未考虑指向空情况

0 赞同 0 条回复

登录以回复

Thaddeus 永久会员 2024年3月5日上午8:59

如果n等于链表长度，即删除链表的头节点，那么此时fast为nullptr，第二个删除操作的while循环就无法进入，pre为nullptr，最后一步就会出现pre->next，解引用空指针的成员。

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        if(head == nullptr) return head;
        ListNode* fast = head;
        ListNode* slow = head;
        while(n--) {
            fast = fast->next;
        }
        // ** 如果n等于链表长度，即删除链表的头节点，那么此时fast为nullptr，无法进入while循环 **
        if(fast == nullptr) return head->next;
        while(fast->next != nullptr) {
            fast = fast->next;
            slow = slow->next;
        }
        slow->next = slow->next->next;
        return head;
    }
};

0 赞同 0 条回复

南梁陈庆之普通 2024年3月5日上午12:14

如果删除的是第一个节点，会出现空指针情况

0 赞同 0 条回复

登录以回复
　南木普通 2024年3月4日下午8:37

fast指针未考虑指向空情况

0 赞同 0 条回复

登录以回复
一颗红豆普通 2024年3月4日下午8:02

没有考虑空指针

0 赞同 0 条回复

登录以回复
mpweixin用户普通 2024年3月4日下午5:51

没有考虑头节点

0 赞同 0 条回复

登录以回复

Jankin 普通 2024年3月4日下午5:51

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

/**
 * Definition for singly-linked list.
 * public class ListNode {
 * int val;
 * ListNode next;
 * ListNode() {}
 * ListNode(int val) { this.val = val; }
 * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if (head == null)
            return null;
        ListNode dummy = new ListNode(0, head);
        ListNode slow = dummy, fast = head;
        for (int i = 0; i < n; i++) {
            fast = fast.next;
        }
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;
        return dummy.next;
    }
}

时间复杂度：O（n）
空间复杂度：O（1）

0 赞同 0 条回复

kfaebot 普通 2024年3月4日下午3:49

没有考虑头节点为空指针的情况，最好再设一个虚拟头节点

0 赞同 0 条回复

登录以回复
Raphtalia. 普通 2024年3月4日下午1:27

没有考虑空指针

0 赞同 0 条回复

登录以回复
零普通 2024年3月4日上午12:22

忽略了边界值，会出现空指针异常

0 赞同 0 条回复

登录以回复
叫不醒装睡的人普通 2024年3月3日下午10:36

未考虑空指针情况。while 循环中删除头节点处理不妥当

0 赞同 0 条回复

登录以回复
神经蛙普通 2024年3月3日下午10:10

删除是头节点的时候，prev是空指针

0 赞同 0 条回复

登录以回复
东普通 2024年3月3日下午10:10

pre节点初始设置为null，如果要删除的是头节点就会出错

0 赞同 0 条回复

登录以回复
白雪公主倒拔垂杨柳永久会员 2024年3月3日下午7:31
1. 没有对头结点为空的情况进行判断
2. 没有对链表长度不足n的情况进行处理
0 赞同 0 条回复

登录以回复
墨丘俐普通 2024年3月3日下午7:14

删除的是head的时候，会出现空指针异常/

0 赞同 0 条回复

登录以回复
一期一会普通 2024年3月3日下午6:56

要进行删除操作，最好使用带有头结点的链表，因为在寻找结点的第一个while中，如果删除第一个结点的话，fast就指向了nullptr，无法进行第二个while

0 赞同 0 条回复

登录以回复
lucky耶耶耶*👻*～普通 2024年3月3日下午5:59
```
没有考虑空指针问题
```
0 赞同 0 条回复

登录以回复
Laboratory 普通 2024年3月3日下午5:30

如果删除的是头节点，则出错

0 赞同 0 条回复

登录以回复

Jimmy 普通 2024年3月3日上午11:33

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode *dummyHead = new ListNode(0);//防止删除头节点，构造虚拟节点
        dummyHead->next = head;
        ListNode *slow = dummyHead,*fast = dummyHead;
        while(n-- && fast != nullptr){
            fast = fast->next;
        }
        fast = fast->next;//fast多走一步，让slow移到删除节点的前面一个节点
        while(fast){
            slow = slow->next;
            fast = fast->next;
        }

        slow->next = slow->next->next;
        return dummyHead->next;

    }

};

0 赞同 0 条回复

😴 普通 2024年3月3日上午10:04

在while循环过程中，没有考虑链表是否有n个元素，遍历时可能为空

0 赞同 0 条回复

登录以回复
云无深雁影普通 2024年3月3日上午10:03

未考虑边界情况，指针指向null

0 赞同 0 条回复

登录以回复
方铎码农普通 2024年3月3日上午9:47

问题：边界处理，若要删除的是头结点，那么slow和pre指向的是同一个节点，可能会出错
修改方法：开一个虚拟的头结点放在head前面，pre指向此虚拟头结点

0 赞同 0 条回复

登录以回复
Yox 普通 2024年3月3日上午6:05

没有考虑空指针问题

0 赞同 0 条回复

登录以回复
机电皮怪永久会员 2024年3月2日下午11:57

“`CPP
//需要考虑边界处理

0 赞同 0 条回复

登录以回复

言之命至普通 2024年3月2日下午10:27

如果删除的是第一个节点，那么此时pre为 null，最后调用 pre.next 就会出问题。

改正之后：

    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0);//先创建虚拟头节点
        dummy.next = head;
        ListNode pre=dummy;//pre用于表示 slow 前面一个
        ListNode fast = head;
        ListNode slow = head;

        // 让第一个指针先移动n步
        for (int i = 1; i <= n ; i++) {
            fast = fast.next;
        }

        // 然后同时移动两个指针，直到第一个指针到达末尾
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
            pre=pre.next;
        }

        // 删除slow指针指向的节点
        pre.next = slow.next;

        return dummy.next;
    }

0 赞同 0 条回复

NULL 普通 2024年3月2日下午9:57

一定要考虑null的问题

0 赞同 0 条回复

登录以回复
heathhou 普通 2024年3月2日下午9:39

如果删除的是第一个节点，那么此时pre没有指向第一个节点的前驱结点。应该使用一个虚拟头结点。

0 赞同 0 条回复

登录以回复
进取普通 2024年3月2日下午9:16

感觉涉及到链表插入删除的时候做一个虚拟头节点会好很多

0 赞同 0 条回复

登录以回复
王位詮釋普通 2024年3月2日下午8:49

视频中代码将pre初始设置为null，如果需要删除的节点为倒数第n个，也就是第1个，这时候pre.next=slow.next就会有空指针异常，感觉单独进行判断或者初始化时候添加一个头指针辅助可能可以解决

0 赞同 0 条回复

登录以回复
是hua不是pua 普通 2024年3月2日下午8:17

边界情况，当删除第一个节点的时候，第一个while的fast其实已经为空了。第二个while不会继续执行。

0 赞同 0 条回复

登录以回复
紫芝普通 2024年3月2日下午6:21

感觉视频中这段代码没有考虑当n为链表长度时的情况，这是在while循环后，fast始终是指向空指针的，则第二个循环始终无法进入，pre就会是空指针。

0 赞同 0 条回复

登录以回复

# 回答此问题取消回复

后才能回答

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

共以下 35 个回答

# 回答此问题 取消回复

# 回答此问题取消回复