一、题目说明

这个题目是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;

		}

};