编写删除链表倒数第N个节点的代码出现空指针异常，求排查原因

你的代码如下：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

int isfound(struct ListNode* head, int i );

int isfound(struct ListNode* head, int i )
{
    while(i--)
    {
        if(head == NULL) return 0;
        head = head->next;
    }
    head = head->next ;
    return (head == NULL)? 1 : 0 ;
}

struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
    
    struct ListNode* temp = head ;
    struct ListNode* prev = NULL ;
    if(isfound(head,n+1))
    {
        head = NULL;
        return head;
    }
    while( temp != NULL)
    {
        
        if(isfound(temp,n))
        {
            temp->next = temp->next->next;
            return head;
        }
        prev = temp ;
        temp = temp->next; 
    }

    return head;

}

空指针异常的核心原因 #

异常出在isfound函数的head = head->next;这一行：当循环i--结束后，head有可能已经是NULL，此时直接访问head->next属于非法内存访问，触发空指针异常。

举个典型场景：链表只有1个节点，要删除倒数第1个节点（即头节点）。此时调用isfound(temp,1)：

1. 循环i--执行1次，head从唯一节点变成NULL
2. 循环结束后直接执行head = head->next，此时head是NULL，访问next直接触发异常

另外你处理头节点的逻辑也有误：就算没触发空指针，把head设为NULL也不对，应该返回原头节点的下一个节点。

修正方案 #

方案1：修复原逻辑 #

先解决isfound的空指针问题，再调整头节点删除逻辑：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

int isfound(struct ListNode* head, int i )
{
    while(i--)
    {
        if(head == NULL) return 0;
        head = head->next;
    }
    // 循环结束后先判断head是否为NULL，再访问next
    if (head == NULL) return 1;
    return (head->next == NULL) ? 1 : 0;
}

struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
    
    struct ListNode* temp = head ;
    // 判定是否要删除头节点
    if(isfound(head, n))
    {
        struct ListNode* newHead = head->next;
        free(head); // 释放节点内存，避免泄漏
        return newHead;
    }
    while( temp != NULL)
    {
        if(isfound(temp,n))
        {
            struct ListNode* toDelete = temp->next;
            temp->next = temp->next->next;
            free(toDelete); // 释放被删节点内存
            return head;
        }
        temp = temp->next; 
    }

    return head;

}

方案2：双指针法（更高效，一次遍历） #

这种方法无需辅助函数，通过虚拟节点避免特殊处理头节点，逻辑更简洁：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
    struct ListNode dummy;
    dummy.next = head;
    struct ListNode *fast = &dummy;
    struct ListNode *slow = &dummy;

    // 快指针先走n+1步
    for(int i=0; i<=n; i++){
        fast = fast->next;
    }

    // 快慢指针同步移动，直到快指针到末尾
    while(fast != NULL){
        fast = fast->next;
        slow = slow->next;
    }

    // 删除目标节点并释放内存
    struct ListNode* toDelete = slow->next;
    slow->next = slow->next->next;
    free(toDelete);

    return dummy.next;
}

内容的提问来源于stack exchange，提问作者Nanda Kumar