【面试经典 150 | 链表】删除链表的倒数第 N 个结点

文章目录

写在前面
Tag
题目来源
解题思路
- 方法一：统计节点个数
- 方法二：双指针
写在最后

写在前面

本专栏专注于分析与讲解【面试经典150】算法，两到三天更新一篇文章，欢迎催更……

专栏内容以分析题目为主，并附带一些对于本题涉及到的数据结构等内容进行回顾与总结，文章结构大致如下，部分内容会有增删：

Tag：介绍本题牵涉到的知识点、数据结构；
题目来源：贴上题目的链接，方便大家查找题目并完成练习；
题目解读：复述题目（确保自己真的理解题目意思），并强调一些题目重点信息；
解题思路：介绍一些解题思路，每种解题思路包括思路讲解、实现代码以及复杂度分析；
知识回忆：针对今天介绍的题目中的重点内容、数据结构进行回顾总结。

Tag

【链表-删除节点】【迭代】

题目来源

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

解题思路

方法一：统计节点个数

思路

一种朴素的方法是首先统计链表中节点的个数 m，倒数第 n 个节点就是正数第 m - n + 1 个节点。我们从头结点开始，找到正数第 m - n 个节点（要删除节点的前一个节点），直接将该节点的指针指向下下个节点即可。

代码

/*** Definition for singly-linked list.* 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) {}* };*/
class Solution {
public:const int getLength(ListNode* head) {int len = 0;while (head) {++len;head = head->next;}return len;}ListNode* removeNthFromEnd(ListNode* head, int n) {ListNode* dummy = new ListNode(0, head);int m = getLength(head);ListNode* cur = dummy;for (int i= 0; i < m - n; ++i) {cur = cur->next;}cur->next = cur->next->next;return dummy->next;}
};

复杂度分析

时间复杂度： $O (m)$ ， $m$ 为链表的长度。

空间复杂度： $O (1)$ 。

方法二：双指针

思路

我们先用一个指针指向链表的第 n 个节点，此时增加另一个指针指向头结点，接着让两个指针同时向链表尾部移动，每一移动一个位置，当第一个指针到达 nullptr 时，我们也就找到了需要删除的节点。

如果我们利用代码中的 while 循环就找到了要删除节点的上一个节点，此时直接将该节点的指针指向下下个节点即可。

代码

/*** Definition for singly-linked list.* 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) {}* };*/
class Solution {
public:ListNode* removeNthFromEnd(ListNode* head, int n) {ListNode *first = head;ListNode *dummy = new ListNode(0, head);ListNode *second = dummy;for(int i = 0; i < n; ++i)first = first->next;while(first){first = first->next;second = second->next;}second->next = second->next->next;return dummy->next;}
};

复杂度分析

时间复杂度： $O (m)$ ， $m$ 为链表的长度。

空间复杂度： $O (1)$ 。