【数据结构】【线性表】【练习】删除链表倒数第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.
分析题目信息
其次观察题目，我们可以获得一些信息：
- 该链表为无头结点的单链表，因此删除过程中需要注意第一个结点的删除与其他结点有些许不同。
- 该链表删除结点位置是倒着数的，但是单链表是不可逆的；因此在删除时要找到需要删除的位置，必须知道链表总长length，然后遍历链表到length-n个位置，进行删除。
解题思路
根据上述的信息我们解决该问题的大致思路是：
- 遍历链表，获取链表总长信息length
- 找到要被删除结点的前驱结点length-n
- 修改前驱结点的next
- 释放要删除的结点空间
代码解析
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个结点在哪？找到末尾结点指针又在最后了，单链表又不可逆，又得从头遍历。好像只能遍历两遍。
我们重新审视一下这个问题：
- 我们必须找到末尾结点，以便确认倒数第n个结点的位置，此时结构体指针在结尾。
- 因为单链表不可逆，我要让指针到倒数第n个结点需要重新遍历。
双指针
归根结底就是因为一个指针无法在单链表中倒着走，那么我是不是可以加一个指针呢？让一个指针跟在另一个指针的屁股后面，距离为n。
例如：
当前面那个指针指向最后一个结点时，后面那个指针刚好在倒数第n个结点的前驱结点那里。
例如：
这样的话就只需要遍历一次链表就能实现删除链表的倒数第n个结点；
双指针解题思路
- 创建虚拟头结点
- 创建前后双指针
- 令后指针after指向头结点L，前指针超过后指针n个位置
- 前后指针同时向前，直到former到最后一个结点，此时after到达要被删除结点的前驱结点
- 修改after的next
- 释放空间
代码解析
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;
}好的各位，这个题目暂时就讲到这里，如果大家有新的题目或者有新的思路，欢迎各位大佬评论或私信。