给定一个链表，删除链表的倒数第 n 个节点并返回链表的头指针
例如，
例如，
给出的链表为: 
, 
.
删除了链表的倒数第
个节点之后,链表变为
.
删除了链表的倒数第
数据范围： 链表长度 
，链表中任意节点的值满足 
要求：空间复杂度 )
，时间复杂度 )
备注：
备注：
题目保证 一定是有效的
[编程题]删除链表的倒数第n个节点
struct ListNode* removeNthFromEnd(struct ListNode* head, int n ) {
// write code here
struct ListNode *fast,*slow;
fast=slow=head;
for(int i=1;i<=n;i++)
fast=fast->next;
if(fast == NULL)
return head->next;
while(fast->next!=NULL){
fast = fast->next;
slow = slow->next;
}
//free(slow);
slow->next = slow->next->next;
return head;
// write code here
struct ListNode *fast,*slow;
fast=slow=head;
for(int i=1;i<=n;i++)
fast=fast->next;
if(fast == NULL)
return head->next;
while(fast->next!=NULL){
fast = fast->next;
slow = slow->next;
}
//free(slow);
slow->next = slow->next->next;
return head;
}
删除完某个节点不应该要free掉吗，为什么加了free不行，不加却可以
发表于 2022-06-06 20:58:06
回复(1)
方案:跟找到倒数第k个节点有所不同,主要是需要设置一个虚拟节点,用来记录第k个节点的前一个节点.
import java.util.*;
/*
* public class ListNode {
* int val;
* ListNode next = null;
* }
*/
public class Solution {
/**
*
* @param head ListNode类
* @param n int整型
* @return ListNode类
*/
public ListNode removeNthFromEnd (ListNode head, int n) {
// write code here
//需要设置一个虚拟节点
ListNode v = new ListNode(-1);
//虚拟节点指向头结点
v.next = head;
//使用双指针的方案
ListNode last = head;
ListNode nodeN = v;
int index = 1;
while(last != null){
last = last.next;
if(index > n) nodeN = nodeN.next;
index ++;
}
//执行删除操作
ListNode temp = nodeN.next;
nodeN.next = temp.next;
return v.next;
}
}
发表于 2022-04-30 15:28:21
回复(0)
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
class Solution {
public:
/**
*
* @param head ListNode类
* @param n int整型
* @return ListNode类
*/
ListNode* removeNthFromEnd(ListNode* head, int n) {
// write code here
ListNode *dummy_head = new ListNode(-1);
dummy_head->next = head;
ListNode *fast=head, *slow=dummy_head;
while(n) {
fast = fast->next;
--n;
}
while(fast) {
fast = fast->next;
slow = slow->next;
}
slow->next = slow->next->next;
return dummy_head->next;
}
};
dummy_head简化条件判断
slow-->next指向实际需要删除的节点，节省一个中间变量
发表于 2022-02-10 11:43:32
回复(0)
简单的递归
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
class Solution {
public:
/**
*
* @param head ListNode类
* @param n int整型
* @return ListNode类
*/
ListNode* removeNthFromEnd(ListNode* head, int n) {
int count = 0;
return removeNth(head, n, count);
}
ListNode* removeNth(ListNode* head, int n, int& count) {
if (!head) return nullptr;
head->next = removeNth(head->next, n, count);
count++;
if (count == n) return head->next;
return head;
}
};
发表于 2022-01-03 22:57:30
回复(0)
func removeNthFromEnd( head *ListNode , n int ) *ListNode {
// write code here
var (
fast *ListNode = head
slow *ListNode = head
pre *ListNode
)
// if n <=0 {
// return head
// }
for i:= 0 ; i < n-1 ; i++{
fast = fast.Next
// if fast.Next == nil{
// break
// }
}
for fast.Next != nil {
pre = slow
slow = slow.Next
fast = fast.Next
}
if pre == nil {
return head.Next
}else{
pre.Next = slow.Next
}
return head
}
发表于 2021-12-14 07:35:27
回复(0)
//就是一个走到n位置，另一个和他一起走，那么就倒数了
public ListNode removeNthFromEnd (ListNode head, int n) {
ListNode node=head;
ListNode fast=head;
int count=0;
while (count<n){
fast= fast.next;
if(fast==null) return head.next;
count++;
}
while (fast.next!=null){
fast=fast.next;
node=node.next;
}
node.next=node.next.next;
return head;
}
发表于 2021-12-02 15:54:18
回复(0)
// 将链表各个节点的顺序存入map对象中，然后找到倒数第n - 1和倒数第n+1个进行连接操作
function removeNthFromEnd( head , n ) {
// write code here
const map = new Map()
let cur = head
let i = 0
while (cur) {
map.set(i, cur)
i ++
cur = cur.next
}
const pre = map.get(i - n - 1)
const next = map.get(i - n + 1)
if (!pre) return head.next
pre.next = next
return head
}
发表于 2021-11-18 16:53:42
回复(0)
import java.util.*;
/*
* public class ListNode {
* int val;
* ListNode next = null;
* }
*/
public class Solution {
/**
*
* @param head ListNode类
* @param n int整型
* @return ListNode类
*/
public ListNode removeNthFromEnd (ListNode head, int n) {
// write code here
ListNode cur=head;
ListNode fast=head;
for(int i=0;i<n;i++){
fast=fast.next;
if(fast==null) return head.next;
}
while(fast.next!=null){
cur=cur.next;
fast=fast.next;
}
cur.next=cur.next.next;
return head;
}
}
发表于 2021-11-15 21:59:56
回复(0)
ListNode* removeNthFromEnd(ListNode* head, int n) {
int i, length = 0;
struct ListNode* L; //返回表
struct ListNode* c; //用于遍历链表求表长
struct ListNode* pre; //工作指针前驱
struct ListNode* p; //工作指针
struct ListNode* q; //释放被删节点
if(head == NULL || head->next == NULL){ //表为空或仅有1个结点，必然返回空表
return NULL;
}else {
pre = head;
c = head;
L = head;
p = head->next;
while(c != NULL){
length++; //求表长
c = c->next;
}
if(n == length){ //删除首节点，
q = pre;
L = L->next;
free(q);
return L;
}else{ //删除非首节点
for(i = 1; i < length - n; i++) //将p指向需删结点，pre作为前驱跟随
{
pre = pre->next;
p = p->next;
}
if(p->next == NULL){ //若为尾节点，直接将pre指针域置空
q = p;
pre->next = NULL;
free(q);
}else{ //非尾节点普通删除方法
q = p;
p = p->next;
pre->next = p;
free(q);
}
}
}
return L;
}
发表于 2021-08-27 18:32:27
回复(0)
//必须要考虑到内存的释放，要不然手撕代码可能被鄙视
ListNode* removeNthFromEnd(ListNode* head, int n) {
// write code here
if(NULL == head || n <= 0)
return NULL;
ListNode* first = head;
ListNode* last = head;
for(int i=1; i < n ;i++)
{
last = last->next;
if(last == NULL)
return NULL;
}
//链表长度就为n，删除首结点
if(last->next == NULL)
{
//占存不用的结点，好释放
ListNode* temp = head->next;
delete(head);
return temp;
}
//last往后移动一个单位这样下一次first就可以少移动一个
last = last->next;
//如果链表长度＞n
while(last->next != NULL)
{
last = last->next;
first = first->next;
}
//占存结点并释放。不能直接释放first->last，会出错的的。
ListNode* temp = first->next;
first->next = first->next->next;
delete(temp);
return head;
}
发表于 2021-08-25 17:14:03
回复(0)
class Solution {
public:
/**
*
* @param head ListNode类
* @param n int整型
* @return ListNode类
*/
ListNode* removeNthFromEnd(ListNode* head, int n) {
if (nullptr == head) return nullptr;
if (0 == n) return head;
ListNode *dummy = new ListNode(0);
dummy->next= head;
int deleteIndex = sizeOfLinkedListWithListNode(head) - n;
ListNode*cur = dummy;
for (int i=1; i<= deleteIndex ;++i) {
cur = cur->next;
}
cur->next = cur->next->next;
ListNode* ans = dummy->next;
return ans;
}
int sizeOfLinkedListWithListNode(ListNode* head) {
if(nullptr == head) return 0;
ListNode* cur = head;
int size = 0;
while(cur) {
size++;
cur = cur->next;
}
return size;
}
}; 思路1: 删除链表倒数第k个节点，第一步获取链表的长度length,转化为删除正向第length-k序号对应 的元素，比如1 2 3 4 5，删除倒数第二个元素即4，也就是正常找到序号为3（length - 2）值为3的节点，将3的next指针指向5节点，然后销毁4节点即可
发表于 2021-04-20 13:40:54
回复(0)
思路：先从头节点开始走n步，然后再找另一个节点从头节点开始走，
前后两个节点同时走，确定倒数第n个节点的位置，然后进行删除
public class Solution {
/***
* @param head ListNode类
* @param n int整型
* @return ListNode类
*/
public ListNode removeNthFromEnd (ListNode head, int n) {
// write code here
ListNode cur=head;
ListNode help=head;
ListNode pre=head;
while(n--!=0){
pre=cur;
cur=cur.next;
}
if(cur==null){
return head.next;
}
while(cur!=null){
pre=help;
help=help.next;
cur=cur.next;
}
pre.next=help.next;
return head;
}
}
发表于 2021-03-13 13:09:00
回复(0)
试图不用双指针，用大空间来换时间，不过最后还是3ms没能到2ms。
用map来记录位置和对应的节点，倒数转换为正数，直接取值，去节点。（首节点单独处理）
class Solution {
public:
/**
*
* @param head ListNode类
* @param n int整型
* @return ListNode类
*/
ListNode* removeNthFromEnd(ListNode* head, int n) {
// write code here
int len_List = 0;
map<int, ListNode*> index_node;
ListNode* temp = head;
while (temp != NULL) //放进map里，长度查询好了
{
index_node[len_List + 1] = temp;
len_List++;
temp = temp->next;
}
if (n == len_List) //如果是第一位
return head->next;
int index = len_List - n; //查询正确的map位置
temp = index_node[index];
temp->next = temp->next->next;
return head;
}
};
编辑于 2021-01-19 10:40:43
回复(0)
ListNode* removeNthFromEnd(ListNode* head, int n) {
// write code here
ListNode *pos=head;
ListNode *prev=NULL;
ListNode *res=head;
while(n--)
{
pos=pos->next;
}
while(pos)
{
prev=res;
res=res->next;
pos=pos->next;
}
if(prev==NULL) return res->next;
prev->next=res->next;
return head;
} 简洁的快慢指针法
发表于 2020-12-17 21:08:02
回复(0)
整体思路并不复杂，使用双指针标记即可，
难点在于要理清楚，距离和循环边界条件
及注意特殊情况，删除头节点时的处理
import java.util.*;
/*
* public class ListNode {
* int val;
* ListNode next = null;
* }
*/
public class Solution {
/**
*
* @param head ListNode类
* @param n int整型
* @return ListNode类
*/
public ListNode removeNthFromEnd (ListNode head, int n) {
// write code here
if(head==null){
return null;
}
//新 new 一个节点指向头节点，为待删节点前一个节点
ListNode preNeedDel=new ListNode(0);
preNeedDel.next=head;
//标记需要删除的节点
ListNode needDel=head;
//标识最后一个节点
ListNode end=head;
//标识删除的倒数第 n 个节点
int i=0;
while(end!=null){
//先拉开 n 个距离 注意这里 end 会走到 null
if(i<n){
end=end.next;
i++;
}else{
end=end.next;
preNeedDel=preNeedDel.next;
needDel=needDel.next;
}
}
preNeedDel.next=preNeedDel.next.next;
//注意删除头节点情况
if(needDel==head){
return preNeedDel.next;
}
return head;
}
}
编辑于 2020-11-29 10:10:18
回复(0)
import java.util.*;
/*
* public class ListNode {
* int val;
* ListNode next = null;
* }
*/
public class Solution {
/**
*
* @param head ListNode类
* @param n int整型
* @return ListNode类
*/
public ListNode removeNthFromEnd (ListNode head, int n) {
ListNode root = new ListNode(-1);
root.next = head;
// 方便处理头节点的删除
ListNode pi = root, pk = root;
// 先使 pi 前进 n 步，确保 pk 和 pi 相差 （n），当 pi 走到末尾的时候，pk 就是倒数第 n + 1 个节点,直接删除pk后面的节点即可
for(int i = 0; i < n; i++) {
pi = pi.next;
}
while(pi.next != null) {
pi = pi.next;
pk = pk.next;
}
// 删除 pk 后面的节点
pk.next = pk.next.next;
return root.next;
}
}
发表于 2020-11-26 10:24:02
回复(0)
import java.util.*;
/*
* public class ListNode {
* int val;
* ListNode next = null;
* }
*/
public class Solution {
/**
*
* @param head ListNode类
* @param n int整型
* @return ListNode类
*/
public ListNode removeNthFromEnd (ListNode head, int n) {
// write code here
ListNode p = head;
ListNode q = p;
int count = 1;
//先判断只有一个节点的情况
if(p.next == null ){
return null;
}
//节点数大于1
else if(p.next != null){
//count为总共节点数
while(q.next!=null){
count++;
q = q.next;
}
//删除的是否是第一个节点
if(n == count){
head = head.next;
}
//删除的不是第一个节点
else{
//p移动到要删除节点的前一个位置
for(int i = 1;i<count-n;i++){
p = p.next;
}
//删去节点
q = p.next;
p.next = q.next;
}
}
return head;
}
} 非间隔指针的方法
发表于 2020-10-14 14:05:42
回复(0)
ListNode* removeNthFromEnd(ListNode* head, int n) {
// write code here
if (head == NULL) {
return NULL;
}
ListNode* leader = head;
ListNode* slow = head;
for (int i = 0; i < n;i++) {
leader = leader->next;
}
if (leader == NULL) {
return head->next;
}
while (leader->next) {
leader = leader->next;
slow = slow->next;
}
slow->next = slow->next->next;
return head;
}
// write code here
if (head == NULL) {
return NULL;
}
ListNode* leader = head;
ListNode* slow = head;
for (int i = 0; i < n;i++) {
leader = leader->next;
}
if (leader == NULL) {
return head->next;
}
while (leader->next) {
leader = leader->next;
slow = slow->next;
}
slow->next = slow->next->next;
return head;
}
发表于 2020-10-12 18:03:26
回复(0)
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
class Solution {
public:
/**
*
* @param head ListNode类
* @param n int整型
* @return ListNode类
*/
ListNode* removeNthFromEnd(ListNode* head, int n) {
// 为了防止是删除第一个节点 所以增加一个新的节点指向头结点
ListNode* hh = new ListNode(-1);
hh->next = head;
int len = 0;
ListNode* pre = head;
while(pre != nullptr)
{
len++;
pre = pre->next;
}
// 得到删除节点的前一个节点的位置
int erase_idx = len - n;
if(len == 1) return nullptr;
pre = hh;
// 移动到删除节点的头一个节点的位置
for(int i = 0; i < erase_idx; i++) pre = pre->next;
// 进行删除操作
pre->next = pre->next->next;
//返回值
return hh->next;
}
};
发表于 2020-09-03 15:35:11
回复(0)
问题信息
难度：
383条回答
618收藏
21001浏览
通过挑战的用户
-
2023-01-19 22:07:50 -
2022-12-24 16:46:23
-
2022-12-05 16:30:38 -
2022-11-29 13:29:59 -
2022-11-28 18:17:15
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
