前言

今天继续学习算法，前几天觉得数组的题还是简单了，今天换个链表的，没想到也是考研期间学过的比较经典的链表算法，就当复习cpp啦！

我的思路

首先我觉得大家应该已经懂了链表是怎么实现删除的，假设待删除的Lnode的前指针是pre，只需要pre -> next= pre->next->next即可。

思路一

我们最常见的思路是把倒数变成正数，所以如果我们能知道链表的长度，那倒数第一个不就是正数最后一个吗，倒数第k个就是正数第n-k+1。这个思路需要遍历2次。

思路二

另一种思路也很经典，我们需要两个指针，假设我们要找第2个元素，那么两个指针一前一后遍历，当前一个指针遍历到链表的最后一个元素时，后一个指针自然就指到倒数第二个元素了（注意删除的时候需要pre指针）。总的来说，我们需要两个指针之间的间距是（k-2），或者让一个指针从头结点开始，先走k个距离。

我的代码

#include<iostream>using namespace std;typedef struct Lnode {int x;struct Lnode* next;Lnode(int val) :x(val), next(NULL) {}
};int main() {cout << "请输入链表的总数" << endl;int node_num;cin >> node_num;int node;//把链表的总长度存储在头结点的数据域Lnode* head = new Lnode(node_num);Lnode* p=head;Lnode* q;for (int i = 0; i < node_num; i++) {cin >> node;q = new Lnode(node);p->next = q;p = p->next;}p = head -> next;//输出生成的链表while (p ->next!= NULL) {cout << p->x<<" -> ";p = p->next;}cout << p->x;cout << "\n请输入您想删除倒数第几个节点" << endl;int del_place;cin >> del_place;if (del_place > node_num) {cout << "对不起，您输入的值大于链表总长度，删除失败";}else {Lnode* r=head, *s=head;int diff_place = del_place;while (diff_place != 0) {s = s->next;diff_place--;}while (s -> next != NULL) {s = s->next;r = r->next;}Lnode* del_node;del_node = r->next;r->next = r->next->next;delete del_node;del_node = NULL;}p = head->next;//输出生成的链表while (p->next != NULL) {cout << p->x << " -> ";p = p->next;}cout << p->x;}