刷题19. Remove Nth Node From End of List
2024-10-08 12:53:17
一、题目说明
这个题目是19. Remove Nth Node From End of List，不言自明。删除链表倒数第n个元素。难度是Medium！
二、我的解答
链表很熟悉了，直接写代码。
性能如下：
Runtime: 8 ms, faster than 35.76% of C++ online submissions for Remove Nth Node From End of List.
Memory Usage: 8.8 MB, less than 5.26% of C++ online submissions for Remove Nth Node From End of List.
#include<iostream>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution{
public:
ListNode * removeNthFromEnd(ListNode* head,int n){
if(head==NULL) return NULL;
if(n<0) return NULL;
int cur = n;
ListNode*p = head;
ListNode* nTh = p;
while(cur>0 && nTh!=NULL){
nTh = nTh->next;
cur--;
}
//n超过链表长度
if(nTh==NULL && cur>0) return head;
//删除第1个元素
if(nTh==NULL && cur==0){
ListNode * t = p->next;
if(t!=NULL){
head = p->next;
delete p;
return head;
}else{
delete p;
return NULL;
}
}
while(p!=NULL && nTh!=NULL && nTh->next!=NULL){
p=p->next;
nTh = nTh->next;
}
if(p!=NULL){
ListNode * tmp = p->next;
if(p->next !=NULL){
p->next = tmp->next;
}
delete tmp;
}
return head;
}
};
int main(){
Solution s;
ListNode dummy(0);
ListNode *p;
int i = 5;
while(i>0){
ListNode *tmp = new ListNode(i);
tmp->next = dummy.next;
dummy.next = tmp;
i--;
}
p = dummy.next;
while(p!=NULL){
cout<<p->val<<" ";
p=p->next;
}
cout<<endl;
ListNode*r = s.removeNthFromEnd(dummy.next,2);
p = r;
while(p!=NULL){
cout<<p->val<<" ";
p=p->next;
}
cout<<endl;
return 0;
}
三、改进
删除一个变量，性能大幅提高：
Runtime: 4 ms, faster than 88.76% of C++ online submissions for Remove Nth Node From End of List.
Memory Usage: 8.8 MB, less than 5.26% of C++ online submissions for Remove Nth Node From End of List.
改进后代码如下：
#include<iostream>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution{
public:
ListNode * removeNthFromEnd(ListNode* head,int n){
if(head==NULL) return NULL;
if(n<0) return NULL;
int cur = n;
ListNode*p = head;
ListNode* nTh = p;
while(cur>0 && nTh!=NULL){
nTh = nTh->next;
cur--;
}
//n超过链表长度
if(nTh==NULL && cur>0) return head;
//删除第1个元素
if(nTh==NULL && cur==0){
if(p->next!=NULL){
head = p->next;
delete p;
return head;
}else{
delete p;
return NULL;
}
}
while(p!=NULL && nTh!=NULL && nTh->next!=NULL){
p=p->next;
nTh = nTh->next;
}
if(p!=NULL){
ListNode * tmp = p->next;
if(p->next !=NULL){
p->next = tmp->next;
}
delete tmp;
}
return head;
}
};
int main(){
Solution s;
ListNode dummy(0);
ListNode *p;
int i = 5;
while(i>0){
ListNode *tmp = new ListNode(i);
tmp->next = dummy.next;
dummy.next = tmp;
i--;
}
p = dummy.next;
while(p!=NULL){
cout<<p->val<<" ";
p=p->next;
}
cout<<endl;
ListNode*r = s.removeNthFromEnd(dummy.next,2);
p = r;
while(p!=NULL){
cout<<p->val<<" ";
p=p->next;
}
cout<<endl;
return 0;
}
再次改进：
class Solution{
public:
ListNode * removeNthFromEnd(ListNode* head,int n){
if(head==NULL) return NULL;
if(n<0) return NULL;
int len = 0;
ListNode*p = head;
while(p!=NULL){
p = p->next;
len++;
}
//n超过链表长度
if(len<n) return head;
//删除第1个元素
if(len==n){
head = head->next;
return head;
}
int t = len -n -1;
p=head;
while(t-->0){
p=p->next;
}
p->next = p->next->next;
return head;
}
};
最新文章
- Spring中的cglib动态代理
- C#日常总结
- Lua与C++互相调用（上）
- codeforces 451D Count Good Substrings
- 关于Android开发手机连接不上电脑问题解决方案
- docker-containerd 启动流程分析
- C语言redirection
- CommonsChunkPlugin的使用（关于angular2中的polyfills和vendor的疑问解决）
- SQL Insert语句数据以以unicode码存储 解决存储数据出现乱码的问题
- UVa 1363 (数论 数列求和) Joseph's Problem
- Array.splice返回值是数组
- cas改造随笔
- css 圆角效果
- Android应用程序组件Content Provider应用实例
- DLNA_百度百科
- 物理卷操作命令：pvcreate,pvscan,pvdisplay.卷组操作命令：vgcreate,vgdisplay. （转）
- redis中的set集合问题
- CSS3学习系列之盒样式（一）
- [转载] 运维角度浅谈：MySQL数据库优化
- F02 金融学第二定律 资金的积聚