练习题 删除链表的倒数第N个结点

题目

给你一个链表，删除链表的倒数第?n?个结点，并且返回链表的头结点。

示例 1：

输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

示例 2：

输入：head = [1], n = 1
输出：[]

示例 3：

输入：head = [1,2], n = 1
输出：[1]

提示：

• 链表中结点的数目为?sz
• 1 <= sz <= 30
• 0 <= Node.val <= 100
• 1 <= n <= sz

提交代码

提交代码1

//删除链表的倒数第N个结点

//链表->单向搜索
//两个指针一起走，指针1比指针2快一倍

#include<iostream>
using namespace std;

struct ListNode {
	int val;
	ListNode *next;
	ListNode() : val(0), next(nullptr) {}
	ListNode(int x) : val(x), next(nullptr) {}
	ListNode(int x, ListNode *next) : val(x), next(next) {}
};

ListNode *head;//链表头
int n;//倒数第n个节点 

//双指针
void twoPointers(){
	int i = 0,j = 0;//统计两个指针走了多少步 
	//两个指针，p1走1步，p2走两步
	ListNode* p1 = head;
	ListNode* p2 = head;
	
	//移动两个指针 
	while(p2 != nullptr){
		p2 = p2->next;
		j++;
		
		if(p2 != nullptr){
			p2 = p2->next;
			j++;
			p1 = p1->next;
			i++;
		}
	}
	
	//求要删除的节点的位置
	int k = j - n;
	
	//判断要删除的位置在前后哪一段
	if(k <= i){
		//从头节点开始找
		ListNode *last = new ListNode();//记录上一个节点位置
		last->next = head; 
		ListNode *t = head;//遍历链表 
		for(int m = 0;m < k;m++){
			last = t;
			t = t->next;
		}
		last->next = t->next;
		//删除的是头结点的时候 
		if(t == head){
			head = last->next;
		} 
	}else{
		//从i节点开始找 
		ListNode *last;//记录上一个节点位置
		last = p1; 
		ListNode *t = p1->next;//遍历链表 
		i++;
		for(;i < k;i++){
			last = t;
			t = t->next;
		}
		last->next = t->next;
	}
} 

int main(){
	//输入整数数组  
	/*int t; 
	
	while(cin.peek() != '\n'){
		scanf("%d",&t);
		nums.push_back(t);
	}*/
	
	//输入链表
	head = new ListNode();
	ListNode* temp = head;
	int t;//存储节点值
	while(cin.peek() != '\n'){
		scanf("%d",&t);
		ListNode *next = new ListNode(t);
		temp->next = next;
		temp = next;
	}
	head = head->next;
	
	//输入要删除的倒数第几个节点
	scanf("%d",&n); 
	
	//-------------------------------
	
	//双指针
	twoPointers();
	
	//输出结果
	for(ListNode* t = head;t != nullptr;t = t->next){
		printf("%d ",t->val);
	}
	
	return 0;
} 

解题思路：链表具有搜索单向性，要删掉倒数第几个节点，可以遍历一遍链表，知道链表的节点总数，然后确定删除的节点的位置。可以辅助一个指针，指针2每次走两步，指针1每次走1步，指针2到终点时指针1在半程，计算出位置后，判断从头指针开始找删除节点方便还是从指针1开始找方便，从而节省时间。

提交代码2

//删除链表的倒数第N个结点

//链表->单向搜索
//两个指针一起走，指针1比指针2快一倍

#include<iostream>
using namespace std;

struct ListNode {
	int val;
	ListNode *next;
	ListNode() : val(0), next(nullptr) {}
	ListNode(int x) : val(x), next(nullptr) {}
	ListNode(int x, ListNode *next) : val(x), next(next) {}
};

ListNode *head;//链表头
int n;//倒数第n个节点 

//双指针
/*void twoPointers(){
	int i = 0,j = 0;//统计两个指针走了多少步 
	//两个指针，p1走1步，p2走两步
	ListNode* p1 = head;
	ListNode* p2 = head;
	
	//移动两个指针 
	while(p2 != nullptr){
		p2 = p2->next;
		j++;
		
		if(p2 != nullptr){
			p2 = p2->next;
			j++;
			p1 = p1->next;
			i++;
		}
	}
	
	//求要删除的节点的位置
	int k = j - n;
	
	//判断要删除的位置在前后哪一段
	if(k <= i){
		//从头节点开始找
		ListNode *last = new ListNode();//记录上一个节点位置
		last->next = head; 
		ListNode *t = head;//遍历链表 
		for(int m = 0;m < k;m++){
			last = t;
			t = t->next;
		}
		last->next = t->next;
		//删除的是头结点的时候 
		if(t == head){
			head = last->next;
		} 
	}else{
		//从i节点开始找 
		ListNode *last;//记录上一个节点位置
		last = p1; 
		ListNode *t = p1->next;//遍历链表 
		i++;
		for(;i < k;i++){
			last = t;
			t = t->next;
		}
		last->next = t->next;
	}
} */
//优化后的双指针
//指针2比指针1先走n步，则指针2到终点时指针1就是要删除的节点 
void twoPointers(){
	ListNode* p1 = head;
	ListNode* p2 = head;
	ListNode* last = new ListNode();//指针1的上一个节点指针
	
	//指针2先走n步
	for(int i = 0;i < n;i++){
		p2 = p2->next;
	} 
	
	//两个指针一起走
	while(p2 != nullptr){
		last = p1;
		p1 = p1->next;
		p2 = p2->next;
	} 
	
	//删除指针1节点
	last->next = p1->next;
	
	//注意删除的是否是头结点
	if(p1 == head){
		head = last->next;
	} 
} 

int main(){
	//输入整数数组  
	/*int t; 
	
	while(cin.peek() != '\n'){
		scanf("%d",&t);
		nums.push_back(t);
	}*/
	
	//输入链表
	head = new ListNode();
	ListNode* temp = head;
	int t;//存储节点值
	while(cin.peek() != '\n'){
		scanf("%d",&t);
		ListNode *next = new ListNode(t);
		temp->next = next;
		temp = next;
	}
	head = head->next;
	
	//输入要删除的倒数第几个节点
	scanf("%d",&n); 
	
	//-------------------------------
	
	//双指针
	twoPointers();
	
	//输出结果
	for(ListNode* t = head;t != nullptr;t = t->next){
		printf("%d ",t->val);
	}
	
	return 0;
} 

?解题思路：优化多次遍历，利用双指针，指针2先走n步，然后指针2和指针1再一起向后走，直至指针2遍历结束指向空，此时指针1在指针2前n个结点的位置，即倒数第n个结点，删掉指针1即可。