目录

一、题目

二、思路图解

1.找结点

2.没有结点的情况

3.第一个结点

4.其它个结点

三、代码实现

一、题目

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

如下图：（来自LeetCode刷题网）

二、思路图解

1.找结点

题目给出的单链表的题型：他要求我们删除倒数第N个结点，但是单链表的特性是无法进行反向遍历的，所以我们只能通过正向遍历来找到我们所需要删除的结点，将问题从删除倒数第N个结点转化为删除正数第N个结点。

2.没有结点的情况

如果链表是一个空结点、没有可以删除的结点直接返回NULL。

3.第一个结点

当待删除的结点为链表的第一个结点时，即会发生头删。

如图解：先记录头结点的下一个结点，然后再将头指针指向这个结点，再将原头结点空间释放。

 if (head == NULL)//如果链表是空
    {
        return NULL;
    }
    //这个链表的结点个数
    int sz = 0;
    ListNode* phead = head;
    while (phead)
    {
        sz++;
        phead = phead->next;
    }
    //正数的个数
    sz = sz - n + 1;
    //删除这个结点,记录前后结点
    ListNode* cur = head;
    ListNode* prev = head;
    ListNode* next = cur->next;
    phead = head;
    //头删情况
    if (sz == 1)
    {
        phead = next;
        free(cur);

        return phead;
    }

4.其它个结点

如果删除的结点不是第一个结点，我们需要先找到这个结点。

 如图解：记录cur待删除结点的前一个结点prev和后一个结点next, 将prev 链接到 next, 再将cur结点删除就可以了。

        //找到这个节点
        sz -= 1;
        while (sz)
        {
            prev = cur;
            cur = next;
            next = cur->next;
            sz--;
        }

        prev->next = next;
        free(cur);

三、代码实现

typedef struct ListNode ListNode;
struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
    if (head == NULL)
    {
        return NULL;
    }
    //这个链表的结点个数
    int sz = 0;
    ListNode* phead = head;
    while (phead)
    {
        sz++;
        phead = phead->next;
    }
    //正数的个数
    sz = sz - n + 1;
    //删除这个结点,记录前后结点
    ListNode* cur = head;
    ListNode* prev = head;
    ListNode* next = cur->next;
    phead = head;
    //头删情况
    if (sz == 1)
    {
        phead = next;
        free(cur);

        return phead;
    }
    else
    {
        //找到这个节点
        sz -= 1;
        while (sz)
        {
            prev = cur;
            cur = next;
            next = cur->next;
            sz--;
        }

        prev->next = next;
        free(cur);

        return phead;
    }

}