题意概述

• 给定一个链表
• 要求删除倒数倒数第 n 个节点并返回链表的头指针

方法一：双指针

思路与具体做法

• 假设初始pq指针都指向头结点，让p指针先行n步，使得p指针在q指针之后n个结点
• 接着让p，q指针同时遍历，当p指向NULL时，此时q指针应该在p指针前n个结点，也即倒数第n个结点
• 但是删除第n个结点，需要用到第n+1个结点的后继指针，所以让q在初始位置上前移一位即可得到
• 另外新建伪头结点，也可用于删除头结点时的方便返回链表头指针

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* head1=new ListNode(0);//伪头结点，防止删除的是第一个结点,且方便操作
		head1->next=head;
		ListNode *p=head,*q=head1;
		while(n--){//p指针先行n步，使得p指针在q指针之后n个结点 
			p=p->next;
		}
		while(p){
			p=p->next;//p指针指向最后一个结点 
			q=q->next;//q指针指向倒数第n+1个结点 
		} 
		q->next=q->next->next;//删除倒数第n个结点 
		return head1->next; 
    }
};

时间复杂度和空间复杂度分析

• 时间复杂度：$O\left(n\right)O(n)$O(n)，遍历了一次链表
• 空间复杂度：$O\left(1\right)O(1)$O(1)，仅额外新建了一个伪头结点

方法二：栈

思路与具体做法

• 因为栈前进后出特性，容易对链表倒着访问
• 保存所有链表结点后出栈n次，栈顶即为倒数第n+1结点
• 倒数第n+1结点的后继，指向其后继的后继，即删除了第n个结点

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* head1=new ListNode(0);//伪头结点，防止删除的是第一个结点
		head1->next=head;
		stack<ListNode*>s;//保存所有链表结点 
		ListNode* p=head1;//伪头结点也要保存，防止删的是第一个结点 
		while(p){
			s.push(p);
			p=p->next;
		}        
		while(n--){//倒数n个结点全部出栈 
			s.pop();
		} 
		ListNode* t=s.top();//当前栈顶元素即为倒数第n+1 
		t->next=t->next->next;//删除倒数第n个结点 
		return head1->next;
    }
};

时间复杂度和空间复杂度分析

• 时间复杂度：$O\left(n\right)O(n)$O(n)遍历了长度为$nn$n的链表，最坏情况下还要出栈$nn$n次
• 空间复杂度：$O\left(n\right)O(n)$O(n)，栈保存所有链表结点