删除列表的倒数第n个结点，并返回列表头节点

Question

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* removeNthFromEnd(struct ListNode* head, int n) 
{
    struct ListNode* newhead=(struct ListNode*)malloc(sizeof(struct ListNode*));
    newhead=head;
    struct ListNode* slow=newhead;
    struct ListNode* fast=newhead;
    while(n>0)
    {
        if(fast==NULL)
        {
            return NULL;
        }
        fast=fast->next;
        n--;
    }
    while(fast&&fast->next)
    {
        fast=fast->next;
        slow=slow->next;
    }
    slow=slow->next->next;
    return newhead;
}

运行的时候，slow=slow->next->next这一行报错“ member access within null pointer of type 'struct ListNode'”，说试图使用空指针，这段代码要怎么该，好迷

Answer 1

【以下回答由 GPT 生成】

这段代码的问题是在删除倒数第n个节点时，没有正确地处理链接关系。为了删除节点，我们需要将其前一个节点指向其后一个节点，而代码中只是简单地将slow指针指向了下一个节点的下一个节点，而没有正确更新前一个节点的next指针。

以下是我给出的修改方案：

struct ListNode* removeNthFromEnd(struct ListNode* head, int n) 
{
    struct ListNode* newhead = (struct ListNode*)malloc(sizeof(struct ListNode));
    newhead = head;
    struct ListNode* slow = newhead;
    struct ListNode* fast = newhead;
    struct ListNode* prev = NULL;  // 用于记录slow的前一个节点
    int count = 0;  // 用于记录链表长度
    while(n > 0)
    {
        if(fast == NULL)
        {
            return NULL;
        }
        fast = fast->next;
        n--;
        count++;
    }
    while(fast != NULL)
    {
        fast = fast->next;
        prev = slow;
        slow = slow->next;
        count++;
    }
    if (prev == NULL) {  // 删除的节点是头节点
        newhead = newhead->next;
    } else {
        prev->next = slow->next;  // 更新前一个节点的next指针
    }
    free(slow);  // 释放删除节点的内存
    return newhead;
}

下面是对代码修改的说明：

1. 创建了一个新的头节点newhead，并将其指向原来的头节点；
2. 添加了一个指针prev，用于记录slow的前一个节点；
3. 添加了一个循环计数变量count，用于记录链表长度；
4. 在第一个while循环中，除了将fast向前移动n次之外，还将count递增；
5. 在第二个while循环中，没有使用fast->next作为循环条件，而是使用了fast != NULL，这是为了确保slow指向倒数第n个节点；
6. 在第二个while循环中，更新prev指针，并在每轮循环结束时，count递增；
7. 最后，根据prev是否为NULL来判断删除的节点是否为头节点，如果是，则将新的头节点指向头节点的下一个节点；如果不是，则更新prev节点的next指针；
8. 最后，使用free函数释放删除节点的内存。

希望这能帮助你解决问题。如果还有其他问题，请随时询问。

如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^