前言
这道题对于BM8来讲,其实是一个新的解题思路。
主要用到了双指针以及哨兵节点。
题目
描述
给定一个链表,删除链表的倒数第 n 个节点并返回链表的头指针
例如,
给出的链表为: 1 → 2 → 3 → 4 → 5 , n = 2 1→2→3→4→5, n=2 1→2→3→4→5,n=2
删除了链表的倒数第 n n n 个节点之后,链表变为 1 → 2 → 3 → 5 1→2→3→5 1→2→3→5
数据范围: 链表长度 0 ≤ n ≤ 1000 0≤n≤1000 0≤n≤1000,链表中任意节点的值满足 0 ≤ v a l ≤ 100 0≤val≤100 0≤val≤100
要求:空间复杂度 O ( 1 ) O(1) O(1),时间复杂度 O ( n ) O(n) O(n)
备注:
题目保证 n n n 一定是有效的
输入: { 1 , 2 } , 2 \{1,2\},2 { 1,2},2
返回值: { 2 } \{2\} { 2}
解决方案一
1.1 思路阐述
在BM8里面,使用两次遍历的方式找到节点,那么这里其实就只是多个删除的操作,整体代码不难,直接贴下。
看了下题解,这个方法嘛,长度统计法。
1.2 源码
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
//记录链表长度
int length = 0;
//添加表头
ListNode* res = new ListNode(-1);
res->next = head;
//当前节点
ListNode* cur = head;
//前序节点
ListNode* pre = res;
//找到链表长度
while(cur != NULL){
length++;
cur = cur->next;
}
//回到头部
cur = head;
//从头遍历找到倒数第n个位置
for(int i = 0; i < length - n; i++){
pre = cur;
cur = cur->next;
}
//删去倒数第n个节点
pre->next = cur->next;
//返回去掉头节点
return res->next;
}
};
解决方案二
2.1 思路阐述
思路二就是用两个指针,这个在找链表是否有环的时候遇到过。
这里采用双指针,一个快指针一个慢指针,快指针先移动n个节点;
接着两个指针同时移动,当fast指针到达链表尾的时候,slow所指的位置就是要删除的节点了。
这里删除节点对于题目示例1 的情况,存在head和slow指向同一个节点情况,同时删除节点的前驱无法定位,这时候就要用到一个哨兵节点了。
其他的看源码即可。
2.2 源码
#include <cstdlib>
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param head ListNode类
* @param n int整型
* @return ListNode类
*/
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* rec=new ListNode(-1);
ListNode* fast=head;
ListNode* slow=head;
rec->next=head;
int tempN=n-1;
//fast先走n个节点
while (tempN--) {
fast=fast->next;
}
//fast和slow同时走,fast到尾节点则slow的位置就是倒数第n个节点位置
while(fast->next)
{
fast=fast->next;
slow=slow->next;
}
while (head) {
if (head==slow) {
rec->next=head->next;
break;
}
if(head->next==slow)
{
head->next=slow->next;
break;
}
head=head->next;
}
return rec->next;
}
};
总结
BM8,9综合了前面做到的题的思路。
链表题几个思路:双链表,栈,遍历。