【数据结构】【线性表】【练习】删除链表倒数第n个结点

目录

申明

题目

分析题目信息

解题思路

代码解析

技巧解析：创建虚拟头结点

时间复杂度分析

思考：能否只用一趟扫描实现？

双指针

双指针解题思路

代码解析

---

申明

        该题源自力扣题库19，文章内容（代码，图表等）均原创，侵删！

题目

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

示例：n=2，删除倒数第二个链表。

输入：[1,2,3,4,5]

输出：[1,2,3,5]

链表结构体：

struct ListNode {int val;struct ListNode *next;
};

题目相关信息到此为止，我们需要分析一下题目。

回顾链表结点的删除，最重要的步骤是：找到要被删除的结点的前驱结点，修改其next指向要被删除结点的后继结点。例如例题中的要被删除结点为4，因此要将其前驱结点3指向其后继结点5.

分析题目信息

其次观察题目，我们可以获得一些信息：

1. 该链表为无头结点的单链表，因此删除过程中需要注意第一个结点的删除与其他结点有些许不同。
2. 该链表删除结点位置是倒着数的，但是单链表是不可逆的；因此在删除时要找到需要删除的位置，必须知道链表总长length，然后遍历链表到length-n个位置，进行删除。

解题思路

根据上述的信息我们解决该问题的大致思路是：

1. 遍历链表，获取链表总长信息length
2. 找到要被删除结点的前驱结点length-n
3. 修改前驱结点的next
4. 释放要删除的结点空间

代码解析

struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {int length = 0;//初始化链表总长为0/*1.遍历链表，获取链表总长*/struct ListNode* p ;//p表示当前结点p = head;while (p!= NULL) {++length;p = p->next;}/*为了方便删除操作，我们创建一个虚拟头结点*/struct ListNode dummy;dummy.next = head;struct ListNode* prev = &dummy;//prer表示当前结点/*2.遍历链表找到要删除结点的前驱结点*/for (int i=0;i < length - n;i++) {prev = prev->next;}/*3.修改前驱结点的next*/struct ListNode* s = prev->next;//s暂存要被删除结点prev->next = s->next;//修改要被删除结点的前驱结点的next指针/*4.释放要删除的结点空间*/free(s);//释放内存空间return dummy.next;//返回链表头结点
}

技巧解析：创建虚拟头结点

我们再来观察一下是否有头结点的链表的区别：

有头结点的链表：

L为头结点，它和其他结点没有本质上没有区别，但其本身不存储数据，它的next指针指向第一个结点，从第一个结点开始才算链表的真正数据主体。

无头结点的链表：

这里我们需要注意，这里的L不是结点，只是一个指针，它没有next，而是直接指向第一个结点。

        回顾一下链表的插入和删除，非常重要的一个步骤就是：修改被操作结点的前驱结点的next。

        而我们在对无头结点链表的第一个结点进行操作时，找不到其前驱结点，因此需要对其特殊处理，其处理方式和其他结点会有略微差距，因此代码上较为繁杂。而有头结点的存在则不需要考虑第一个结点的问题，相对来说操作更加方便，逻辑更加清晰统一。

        为了使代码操作更具有统一性，我们可以在函数内部创建一个虚拟头结点，将虚拟头指针的next指向原链表的第一个结点，暂时供链表使用。在使用完成后，注意输出时的结点要从虚拟头结点的next结点，摒弃头结点，保持输入输出链表结构的一致性。

时间复杂度分析

        时间复杂度分析当数据量足够大时，影响其时间的往往是最深层的代码，相对而言其它层的可以忽略不记。因此上述方法的时间复杂度主要来自于两个循环语句，while和for。第一个while用于遍历链表获得链表长度数据length，for用于找到链表中要被删除结点的前驱结点(length-n)。

• 最好情况是n=length，要删除结点为第一个结点，时间复杂度为O(1).
• 最坏情况为n=1，要删除结点为最后一个结点，时间复杂度为O(n).
• 平均情况时间复杂度为O(n)

思考：能否只用一趟扫描实现？

        不知道你们是否感觉到两次遍历很麻烦，但不知道链表长度我又不知道倒数第n个在哪，就很矛盾。单链表又是不可逆的，不能从末尾结点去遍历，这可怎么办呢？到这里就陷入一个难题，不找到末尾结点就找不到倒数第n个结点在哪？找到末尾结点指针又在最后了，单链表又不可逆，又得从头遍历。好像只能遍历两遍。

        我们重新审视一下这个问题：

1. 我们必须找到末尾结点，以便确认倒数第n个结点的位置，此时结构体指针在结尾。
2. 因为单链表不可逆，我要让指针到倒数第n个结点需要重新遍历。

双指针

归根结底就是因为一个指针无法在单链表中倒着走，那么我是不是可以加一个指针呢？让一个指针跟在另一个指针的屁股后面，距离为n。

例如：

        当前面那个指针指向最后一个结点时，后面那个指针刚好在倒数第n个结点的前驱结点那里。

例如：

        这样的话就只需要遍历一次链表就能实现删除链表的倒数第n个结点；

双指针解题思路

1. 创建虚拟头结点
2. 创建前后双指针
3. 令后指针after指向头结点L，前指针超过后指针n个位置
4. 前后指针同时向前，直到former到最后一个结点，此时after到达要被删除结点的前驱结点
5. 修改after的next
6. 释放空间

代码解析

struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {/*1.创建虚拟头结点*/struct ListNode dummy;dummy.next = head;/*2.创建前后双指针*/struct ListNode* former;struct ListNode* after;/*3.前后双指针位置初始化*/former=&dummy;for(int i=0;i<n;i++){former=former->next;}after=&dummy;/*4.遍历链表直到former到达末尾结点*/while(former->next!=NULL){after=after->next;former=former->next;}/*5.修改after的next*/struct ListNode* s=after->next;after->next=s->next;/*6.释放空间*/free(s);return dummy.next;
}

好的各位，这个题目暂时就讲到这里，如果大家有新的题目或者有新的思路，欢迎各位大佬评论或私信。