LeetCode第19题删除链表倒数第N个节点运行时错误求助

给定链表的head节点，删除链表的倒数第n个节点并返回链表的头节点。

示例1 #

Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]

约束条件 #

• 链表中的节点数为sz。
• 1 <= sz <= 30
• 0 <= Node.val <= 100
• 1 <= n <= sz

我的代码 #

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode *p=head,*q=head,*t=NULL;
        long long  c=0;
        while(p!=0){
            c++;
            p=p->next;
        }
        c=c-n;
        while(q!=NULL && c>0){
            t=q;
            q=q->next;
            c--;
        }
        t->next=q->next;
        delete q;
        return head;
    }
};

运行错误信息 #

Line 26: Char 12: runtime error: 
         member access within null pointer of type 'ListNode' (solution.cpp)
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior prog_joined.cpp:35:12

错误原因分析 #

这个空指针错误出现在要删除的是链表头节点的场景下。比如测试用例head=[1],n=1：

1. 遍历链表后c=1，计算得c = 1-1=0
2. 第二个循环的条件是c>0，循环不会执行，此时t仍为初始值NULL
3. 执行t->next时，对空指针进行成员访问，直接触发运行时错误

你的代码默认t一定不为空，但忽略了删除头节点的情况——此时目标节点没有前驱节点，t不会被赋值。

修复方案 #

方案1：处理删除头节点的特殊情况 #

在执行t->next前，判断是否要删除头节点：

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode *p=head,*q=head,*t=NULL;
        long long  c=0;
        while(p!=0){
            c++;
            p=p->next;
        }
        c=c-n;
        while(q!=NULL && c>0){
            t=q;
            q=q->next;
            c--;
        }
        if(t == NULL){
            // 删除头节点
            ListNode* newHead = head->next;
            delete head;
            return newHead;
        }
        t->next=q->next;
        delete q;
        return head;
    }
};

方案2：使用虚拟头节点简化逻辑 #

添加虚拟头节点，避免单独处理头节点的特殊情况：

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummy = new ListNode(0);
        dummy->next = head;
        ListNode *p=dummy,*q=dummy;
        long long  c=0;
        while(p!=0){
            c++;
            p=p->next;
        }
        c=c-n-1; // 从虚拟头节点开始计数，需多减1
        while(q!=NULL && c>0){
            q=q->next;
            c--;
        }
        ListNode* toDelete = q->next;
        q->next = toDelete->next;
        delete toDelete;
        ListNode* newHead = dummy->next;
        delete dummy;
        return newHead;
    }
};

优化方案：双指针一次遍历 #

用快慢指针法将时间复杂度优化到O(n)，只需一次遍历：

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummy = new ListNode(0);
        dummy->next = head;
        ListNode* fast = dummy;
        ListNode* slow = dummy;
        
        // 快指针先走n+1步
        for(int i=0;i<=n;i++){
            fast = fast->next;
        }
        
        // 快慢指针一起走，直到快指针到末尾
        while(fast!=NULL){
            fast = fast->next;
            slow = slow->next;
        }
        
        // slow指向要删除节点的前驱
        ListNode* toDelete = slow->next;
        slow->next = toDelete->next;
        delete toDelete;
        
        ListNode* newHead = dummy->next;
        delete dummy;
        return newHead;
    }
};

内容的提问来源于stack exchange，提问作者Akash Suklabaidya