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

本问题对应课程链接：剑指offer刷题第二期

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

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

找错误：面试某大厂手写面试题，找找他错在哪里了？

shuaidi

更新于 4 年前 417 70

共以下 62 个回答

lucca 普通 2022年12月30日上午2:23

1.fast边界
2.用虚拟节点好一点，不用特判

0 赞同 0 条回复

登录以回复
mpweixin用户普通 2022年11月21日下午4:48

没有考虑边界可以加一个虚拟表头

0 赞同 0 条回复

登录以回复
如梦似歌普通 2022年11月7日下午2:52

没有考虑到空指针的问题，特别是当链表只有一个节点的时候，pre->next = slow->next明显会报错。

0 赞同 0 条回复

登录以回复
和普通 2022年10月30日上午8:57

仅有一个结点的时候，pre->next会报错，空指针异常。

0 赞同 0 条回复

登录以回复
你有点可爱喔普通 2022年10月30日上午8:56

边界性问题，没有删除头节点操作

0 赞同 0 条回复

登录以回复
阿白普通 2022年10月29日下午5:14

1、代码写的太难看了
2、不规范，考虑不全

0 赞同 0 条回复

登录以回复
优秀市民普通 2022年10月27日下午8:37

可能为空

0 赞同 0 条回复

登录以回复
cute. 普通 2022年10月27日下午3:55

没考虑空指针异常

0 赞同 0 条回复

登录以回复
symbol 普通 2022年10月26日下午7:02

边界处理

0 赞同 0 条回复

登录以回复
lobort 普通 2022年10月26日下午6:41

fast 可能会遍历到null

0 赞同 0 条回复

登录以回复
潜行1 我是火车王！普通 2022年10月26日下午1:10

以前踩过坑的题目
坑就是不能保证链表可以取到第n个结点
也就是没有考虑如果fast没有走到第n个的情况

0 赞同 0 条回复

登录以回复
努力刷题普通 2022年10月26日上午6:37

没有考虑快指针可能为空

0 赞同 0 条回复

登录以回复
Tolkien 永久会员 2022年10月26日上午1:36

没有考虑当k大于等于链表的长度。当k>=链表长度时，快指针会发生空指针异常。

0 赞同 0 条回复

登录以回复
乱世枭雄普通 2022年10月25日下午6:52

边界异常

0 赞同 0 条回复

登录以回复
@ 普通 2022年10月25日上午10:48

应该弄个虚拟头节点，这样如果删除的是头节点的话就不用进行特殊处理了

0 赞同 0 条回复

登录以回复
晨渊普通 2022年10月25日上午9:04

没有对参数n的边界做处理，n有可能大于链表的节点个数，这时候fast指针等于空，while(n–) { if(fastNULL) return head; fast = fast->next；
}

0 赞同 0 条回复

登录以回复
马啸天永久会员 2022年10月25日上午2:00

1.如果n大于链表长度，会置空

0 赞同 0 条回复

登录以回复
Ruby🗽 普通 2022年10月24日下午11:45

空指针异常

0 赞同 0 条回复

登录以回复
派大星普通 2022年10月24日下午10:51

当n的大小等于链表长度时会遍历到null节点，此时pre未初始化
最后快节点会为null

0 赞同 0 条回复

登录以回复
鸿渐普通 2022年10月24日下午10:50

未考虑当传入的n刚好是链表长度或者大于，这样就会导致空指针异常

0 赞同 0 条回复

登录以回复
庄重普通 2022年10月24日下午10:23

如果n = 链表长度，是要删除头结点，此时无法进行删除，需要用到虚拟头结点

0 赞同 0 条回复

登录以回复
Gg 普通 2022年10月24日下午9:29

面试官好敷衍啊，还说代码写得很好

0 赞同 0 条回复

登录以回复

🚲南下普通 2022年10月24日下午9:04

//第一个while循环中加上判断快指针是否为空的情况
if(fast == nullptr){ 
                return nullptr;
            }

0 赞同 0 条回复

訁訁訁訁訁普通 2022年10月24日下午7:17

当n的大小等于链表长度时会遍历到null节点，此时pre未初始化
正确解决方式：添加虚拟头结点

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if(head == null) return null;
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode cur = dummy;
        ListNode fast =dummy;
        ListNode slow = dummy;
        //因为采用虚拟头结点，所以移动n+1步
        for(int i = 0;i <= n;i++){
            fast = fast.next;
        }   
        while(fast != null){
            slow = slow.next;
            fast = fast.next;
        }
        slow.next = slow.next.next;
        return dummy.next;
    }
}

1 赞同 1 条回复

xye 普通 @ 訁訁訁訁訁 2022年10月25日下午8:21

当n>链表长度时，是不是会删除头指针

登录以回复

cxxz 普通 2022年10月24日下午7:05

应该是没有考虑n大于链表长度和应该从n-1开始–做为while的判断条件

0 赞同 0 条回复

登录以回复
Y7n05h 普通 2022年10月24日下午7:03

当 size n 时会段错误

0 赞同 0 条回复

登录以回复
刺猬普通 2022年10月24日下午4:46

没有考虑到倒数第n个节点是头节点或者甚至n是大于链表长度的情况

0 赞同 0 条回复

登录以回复
忆霁昕永久会员 2022年10月24日下午4:34

在未使用虚拟头结点的情况下，没有对删除的节点是头结点这种情况做特殊处理即sz等于n时。提示中有sz小于等于n，不用考虑fast指针指空的情况。

0 赞同 0 条回复

登录以回复
Whatever 永久会员 2022年10月24日下午3:40

第一个while循环应进行判空，k有可能大于链表长度，导致fast指向空，进而使头结点被删除。

0 赞同 0 条回复

登录以回复

感到自己好渺小普通 2022年10月24日下午2:51

 /*没有判断fast越界问题
倒数第k个结点可能超出链表长度，导致fast为空
在while(n--)里加上if(fast==NULL) return NULL;
*/
class Solution {
public:
    ListNode* getKthFromEnd(ListNode* head, int k) {
    //双指针解法
    ListNode *fast = head;  //设置一个fast指针
    ListNode *slow = head;  //设置一个slow指针
    ListNode *pre = NULL;   //设置一个pre指针用来删除倒数第k个结点
    if(head == NULL)    //判断链表是否为空
    {
        return NULL;
    }
    for(int i = 0;i<k;i++)  //先让快指针先走k步
    {
        if(fast == NULL)
        {
            return NULL;
        }
        fast = fast->next;
    }
    while(fast!=NULL)  //然后快慢指针同步走，直至fast到达NULL，slow到达倒数第K个结点
    {
        pre = slow;
        fast = fast->next;
        slow = slow->next;
    }
    pre->next = slow->next;
    delete slow;  //删除倒数第k个结点
    return head;  //返回head删除倒数第k个结点的链表
    }
};

0 赞同 0 条回复

虾仁猪心普通 2022年10月24日下午2:28

没有考虑倒数第n个节点为头结点时的情况，应该用先创建一个虚拟头结点，让虚拟头结点 dummyHead.next = head

0 赞同 0 条回复

登录以回复

是梦终空永久会员 2022年10月24日下午12:08

第一个while没考虑Fast为空，第二个while要是不执行的话，好像后面pre.next也空指针了，
先定义虚拟头结点，遍历n次，同时后移，返回虚拟头结点的next

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if(head == null)    return null;
        // ListNode pre = new ListNode(0,head);
        ListNode pre = new ListNode(0);
        pre.next = head;
        ListNode slow = pre;
        ListNode fast = head;
        while(n-->0){
            fast = fast.next;
        }     
        while(fast != null){
            slow = slow.next;
            fast = fast.next;
        }
        slow.next = slow.next.next;
        return pre.next;

     }
}

0 赞同 0 条回复

浅夏的无奈普通 2022年10月24日上午8:55

没有判断n为链表长度的情况，导致fast为空

时间复杂度：O(n)
空间复杂度：O(n)

class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        if(head==null){
            return null;
        }
        //创建快慢指针
        ListNode pre=head,cur=head;
        //pre向前跑k个节点
        while(pre!=null&&k>0){
            pre=pre.next;
            k--;
        }
        //两个节点一起跑
        while(pre!=null){
            pre=pre.next;
            cur=cur.next;
        }
        //返回结果
        return cur;
    }
}

0 赞同 0 条回复

啊哈普通 2022年10月24日上午12:48

/**
 * 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 == NULL){return head;}
        ListNode* cur = new ListNode(-1,head);
        ListNode* fast = head, *slow = cur;//slow指向cur 慢走一步，指向倒数N的前一个

        while(n-- && fast){
            fast = fast -> next;

        }
        while(fast != NULL){

            fast = fast -> next;
            slow = slow -> next;
        }
        // 删除节点
        slow->next = slow->next->next;
        return cur->next;
    }
};

时间复杂度O(n)
空间复杂度O(1)
考虑辅助头节点，有可能删除的节点为头节点

0 赞同 0 条回复

酥合普通 2022年10月23日下午10:20

/**
 * 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 fast = head;
        ListNode slow = head;
        for(int i = 1; i < n; i++){
            // n < amount of node in this list
            fast = fast.next;
        }
        ListNode temp = head;
        while(fast.next != null) {

            fast = fast.next;
            temp = slow;
            slow = slow.next;
        }
        if(slow == head){
            return head.next;
        }
        temp.next = temp.next.next;
        return head;
    }
}

边界问题

0 赞同 0 条回复

泡芙永久会员 2022年10月23日下午10:11

没有考虑删除头节点的情况，这里我用虚拟头节点
fast先移动的时候没有考虑fast可能为空的情况
fast应该先移动n+1步

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;

        ListNode fast = dummyHead;
        ListNode slow = dummyHead;
        // fast 先移动 n + 1 步，方便做删除操作
        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 dummyHead.next;
    }
}

0 赞同 0 条回复

T 普通 2022年10月23日下午9:25

没有考虑，n等于链表长度的情况。fast可能会为空。

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        //通过哑结点，这样就不需要对头节点进行特殊判断。
        ListNode dummy = new ListNode(0, head);
        ListNode fast = head, slow = dummy;
        //快指针先走n步
        while(n != 0) {
            fast = fast.next;
            n--;
        }
        while(fast != null) {
            fast = fast.next;
            slow = slow.next;
        }
        // 删除节点
        slow.next = slow.next.next;
        return dummy.next;
    }
}

0 赞同 0 条回复

单个酒窝儿普通 2022年10月23日下午7:55

边界问题没有考虑

0 赞同 0 条回复

登录以回复
追普通 2022年10月23日下午7:02

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

0 赞同 0 条回复

登录以回复
绍熙普通 2022年10月23日下午5:50

边界问题没有考虑

0 赞同 0 条回复

登录以回复
Haoyun 普通 2022年10月23日下午4:56

没考虑中间fast指针可能指向空

0 赞同 0 条回复

登录以回复

晨普通 2022年10月23日下午4:52

如示例2，按照他的代码，while(fast)的循环不会走，pre节点没有被赋值，循环外的pre节点引用会报错

class Solution(object):
    def getKthFromEnd(self, head, k):
        if head == None or head.next == None:
            return None;
        quick, slow = head, head
#使慢指针指向k-1个节点
        while k > 1:
            quick = quick.next
            k -= 1
        while quick:
            quick = quick.next
            slow = slow.next
        slow.next = slow.next.next
        return head

0 赞同 0 条回复

yanshuojune 普通 2022年10月23日下午4:36

需要考虑n为链表长度，即要删除节点为头节点的情况
解体思路：使用快慢指针，fast指针移动n次之后，fast和slow同时移动直到fast移动到尾节点，此时slow指向要删除的倒数第n个节点，删除即可，考虑要删除的节点为头节点的情况，返回head.next
时间复杂度：O(n)
空间复杂度：O(1)

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        # 双指针
        fast, slow = head, head
        count = 0
        while count != n:
            fast = fast.next
            count += 1
        if fast is None:
            return head.next
        else:
            while fast.next:
                fast = fast.next
                slow = slow.next
            temp = slow.next
            slow.next = temp.next
        return head

0 赞同 0 条回复

猫猫真可爱普通 2022年10月23日下午3:52

边界问题，只有一个数据和删除第一个数据的情况

class Solution{
    public ListNode removeNthFromEnd(ListNode head, int n){
        if(head==null||head.next==null){
            return null;
        }
        ListNode p = head,q = head,pre = head;
        for(int i=0;i<n;i++){    
            q=q.next;
        }
        while(q!=null){  
            q=q.next;
            pre=p;         
            p=p.next;
        }
        if(p==head){
            head = head.next;
            return head;
        }else{
            pre.next = pre.next.next;
            return head;
        }

    }
}

0 赞同 0 条回复

Asphyxia 普通 2022年10月23日下午3:29

边界问题，还有就是用一个节点之前首先判断它非空

0 赞同 0 条回复

登录以回复
wxc 普通 2022年10月23日下午12:12

没有考虑删除节点是头节点的情况？

0 赞同 0 条回复

登录以回复

狗蛋儿普通 2022年10月23日上午9:36

私以为删除某个节点，应当找到该节点的前一个节点来进行操作

另外边界处理的地方也是大问题，应当固定边界判别的思维习惯，是指向最后一个节点，还是指向最后一个节点的后一个节点

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode *pre = new ListNode(0);
        pre->next = head;
        ListNode *cur = pre;
        ListNode *res = pre;
        while(n-- && cur) cur = cur->next;
        if(!cur) return nullptr;
        cur = cur->next;
        while(cur){
            cur = cur->next;
            pre = pre->next;
        }
        ListNode *tmp = pre->next;
        pre ->next = pre->next->next;
        delete tmp;
        return res->next;
    }
};

0 赞同 0 条回复

黎昕普通 2022年10月23日上午12:28

没有判断pre为NULL，若pre为NULL，后面pre->next报错

0 赞同 0 条回复

登录以回复

宁永久会员 2022年10月22日下午11:31

删除头节点的时候pre为空，需要添加虚拟头节点。

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummyhead = new ListNode();
        dummyhead.next = head;
        ListNode left = dummyhead;
        ListNode right = dummyhead;
        for(int i = 0; i <= n; i++){
            right = right.next;
        }
        while(right != null){
            left = left.next;
            right = right.next;
        }
        left.next = left.next.next;
        return dummyhead.next;

    }
}

0 赞同 0 条回复

天然普通 2022年10月22日下午11:28

我的思路比较简单暴力，边界问题，长度相同的倒数节点的处理，我的处理方法就是单独拎出来进行处理，代码比较丑陋。。。。

class Solution(object):
    def removeNthFromEnd(self, head, n):
        """
        :type head: ListNode
        :type n: int
        :rtype: ListNode
        """
        temp = head
        slow = temp
        fast = head
        k=0
        while fast!=None:
            k+=1
            fast= fast.next
        fast = head
    
        if k==n:
            h = head.next
            del head
            return h

        for i in range(n-1):
            fast = fast.next

        while fast.next != None:
            slow = temp
            temp = temp.next
            fast = fast.next
        slow.next = temp.next
        del temp

        return head

0 赞同 0 条回复

青木普通 2022年10月22日下午11:19

在不增加头结点的情况下改良这个代码，需要在第一个while后判断fast是否为空，如果为空则直接返回head.next；其他都是对的。我也挂了，下次一定记住加一个头结点:(

0 赞同 0 条回复

登录以回复

波波_1936 普通 2022年10月22日下午10:50

//1 head 为空判断
    //2 ptr 临时指针判空 （可能存在 链表长度为2 k>2）此时tp为null
    public static ListNode deleteKthFromEnd(ListNode head, int k) {
        if (head == null || k == 0) return head;
        ListNode fast = head;
        ListNode slow = head;
        ListNode tp = null;
        while (fast != null) {
            if (k > 0) {
                k--;
                fast = fast.next;
            } else {
                tp = slow;
                fast = fast.next;
                slow = slow.next;
            }
        }
        if (tp != null) {
            tp.next = slow.next;
        }else {
            return slow.next;
        }
        return head;
    }

0 赞同 0 条回复

mpweixin用户普通 2022年10月22日下午10:47

若删除倒数第链表长度个结点，经过第一个while循环后fast指针为空，第二个while循环不会执行。此时pre为空，pre->next会报错。

0 赞同 0 条回复

登录以回复
MR.SandMan 普通 2022年10月22日下午10:39

个人感觉是fast多走了一步

0 赞同 0 条回复

登录以回复
小趴菜永久会员 2022年10月22日下午10:21

判断条件写得不对，应该判断为空，为空的时候跳出循环，遍历找节点时地址为空时停止，在头结点和尾部处理时关注其值是否为空，在执行操作，可以通过虚拟节点即哨兵来解决这个边界问题

0 赞同 0 条回复

登录以回复
西西弗斯的石头永久会员 2022年10月22日下午10:11

如果一共n个节点，删除倒数第n个节点也就是第一个节点会空指针异常，pre最开始指向null，slow指向head，不存在null.next=slow.next，会造成空指针异常，因此需要一个虚拟头节点指向头节点，pre指针虚拟头节点，slow指向head节点，然后思路和他一样就没事了。

0 赞同 4 条回复

登录以回复
- 西西弗斯的石头永久会员 @ 西西弗斯的石头 2022年10月22日下午10:19
  
  而且它最开始的if判断也没判断对，紧张了
  
  登录以回复
- 西西弗斯的石头永久会员 @ 西西弗斯的石头 2022年10月22日下午10:30
  
  倒数第一个节点fast可能为null，slow也可能为null，slow.next又是空指针异常，while循环那改成fast.next
  
  登录以回复
- 西西弗斯的石头永久会员 @ 西西弗斯的石头 2022年10月22日下午10:52
  嘴说还是不靠谱直接再上代码
  
  class Solution { public ListNode removeNthFromEnd(ListNode head, int n) { if(head==null||head.next==null) return null; ListNode headA = new ListNode(0); headA.next = head; ListNode pre = headA; ListNode slow = head,fast = head; int i = n-1; while(i!=0){ fast = fast.next; i--; } while(fast.next!=null){ pre = slow; fast = fast.next; slow = slow.next; } pre.next = slow.next; return headA.next; } }
  登录以回复
- shuaidi 永久会员 @ 西西弗斯的石头 2022年10月22日下午11:09
  
  直接上代码，这个操作很稳
  
  登录以回复
So 普通 2022年10月22日下午9:37

第一个while循环如果n = sz，循环结束fast指向null为空，第二个循环就不会执行

0 赞同 0 条回复

登录以回复
一只骆驼普通 2022年10月22日下午8:28

在删除节点的时候没有考虑到null的情况，可以重新定义一个哑节点去处理，或者可以不处理，直接输出结果。

0 赞同 0 条回复

登录以回复
1ue1uekin8 普通 2022年10月22日下午8:07

fast不为空

0 赞同 0 条回复

登录以回复

194分贝普通 2022年10月22日下午7:56

// 1. fast不为空，不能保证fast->next不为空。
// 2. 经过第一个while循环后，fast可能已经为空，就不会再进入第二个循环，后面delete slow相当于把头结点delete了，return了一个野指针。

1 赞同 0 条回复

Spermalow 普通 2022年10月22日下午7:44

本人比较菜，只找到了一个地方，还是根据视频中的提示才找到。就是面试官问fast指针会不会空的时候，确实是有可能会空的。
比如说，当链表结点长度为3的时候，如果要删除链表中倒数第3个结点（头节点），那么在一开始while(n—) fast=fast->next;就会往后走3步，但是fast一开始是指向head是就是第1个结点。也就是说它最多能走2步，再多走一步就会是空指针。

0 赞同 1 条回复

登录以回复
- 小肸永久会员 @ Spermalow 2022年10月22日下午8:00
  
  交流一下，fast是可以为空的，只是这个程序删除头节点有问题。可以定义一个虚拟头节点dummyHead，dummyHead.next=head；然后定义要删除倒数第n个节点的前驱节点为pre，pre=dummyHead，然后定义一个快指针fast=head，fast先走n步，然后和pre同时走，当fast指向null时，说明fast已经遍历完链表，而pre正好指向倒数第n个节点的前驱节点，也就是倒数第n+1个节点，然后让pre.next = pre.next.next(n不等于0，pre.next就不指向空，这里可以加个判断条件，防止不合法输入)以此来删除倒数第n个节点，然后返回dummyHead.next。
  
  登录以回复
小肸永久会员 2022年10月22日下午7:12

我是Java语言的，C++了解的不多，先说下我找的错误。
1.先说下我找到的他最后修改后的代码第一个明确错误，当链表中只有一个节点，经过两个while()，pre=null，pre->next = slow->next就会报错。
2.再说下我看他刚开始写犯的错误，首先没有判断头节点为空的情况，其次第一次返回的是要删除的节点（第一次面试可能有些紧张）。
写程序时可以注意一些特殊输入，比如空链表，只含一个节点的链表，可以在fast指针走时也判断下fast是否为空。

0 赞同 2 条回复

登录以回复
- Spermalow 普通 @ 小肸 2022年10月22日下午7:34
  
  讨论交流一下
  第一行代码的意思是当head为空的时候返回head
  视频中好像是返回了head，delete了slow
  
  登录以回复
- 小肸永久会员 @ Spermalow 2022年10月22日下午7:43
  
  感谢解答。我是边看边找，这个主要是程序边界值没处理好，比如空链表，只含一个节点的链表。
  
  登录以回复

# 回答此问题取消回复

后才能回答

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

共以下 62 个回答

私以为删除某个节点，应当找到该节点的前一个节点来进行操作

# 回答此问题 取消回复

# 回答此问题取消回复