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

目录

题目描述

方法一：计算链表的长度

方法二：栈

方法三：双指针

---

题目描述

方法一：计算链表的长度

先从头到尾遍历链表，得到链表的长度count，结点编号从1开始起算的话，第(count - n + 1)个结点就是要删除的结点。leetcode官方题解，给出的办法是再遍历一次，遍历到第count-n+1个结点就可以做删除操作了。我用的是用空间换时间，第一次遍历的时候用哈希表把所有结点的地址存起来，哈希键就是结点的序号，这样就不用第二次遍历链表，但同时增加了空间开销。

遍历两次：

/*** 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* dummy = new ListNode(0,head);int length = 0;while(head){++length;head = head->next;}ListNode* cur = dummy;for(int i=0;i < length-n;i++){cur = cur->next;}cur->next = cur->next->next;ListNode* ans = dummy->next;delete dummy;return ans;}
};

题目说结点的数目是1到30个，所以哈希表ListNode* nodes[31]。但是下面的代码是将结点序号从0开始起算的，所以实际上nodes[30]就够了。由于结点的序号从0开始起算，所以要删除的结点就是第(count - 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:ListNode* removeNthFromEnd(ListNode* head, int n) {ListNode* nodes[31];ListNode* cur = head;int count = 0;while(cur){nodes[count++] = cur;cur = cur->next;}int todelete = count - n;if(todelete == 0){return nodes[todelete]->next;}else{nodes[todelete-1]->next = nodes[todelete]->next;}return head;}
};

方法二：栈

遍历链表的时候将所有结点入栈，遍历结束后再从栈弹出n个结点，弹出的第n个结点就是要删除的结点。弹出n个结点之后，栈顶结点就是要删除结点的前驱pre，将pre->next置为pre->next->next即可解决问题。

这种方法巧妙地利用了栈的特性找倒数第n个结点。时间开销上，相当于遍历了两次链表。空间开销也是O(L)。

/*** 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* dummy = new ListNode(0,head);stack<ListNode*> node_stack;ListNode* cur = dummy;while(cur){node_stack.push(cur);cur = cur->next;}for(int i = 0;i < n;i++){node_stack.pop();}ListNode* pre = node_stack.top();pre->next = pre->next->next;ListNode* ans = dummy->next;delete dummy;return ans;}
};

方法三：双指针

使用两个指针遍历链表，快指针fast比慢指针slow超前n个结点。当fast到达链表末尾(为空)时，slow就是倒数第n个结点。只需要遍历一次链表，这种方法才是本题真正要考察的方法，可以和第2095题对比学习2095. 删除链表的中间节点

/*** 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* dummy = new ListNode(0,head);ListNode* fast = head;ListNode* slow = head;ListNode* pre = dummy;//fast比slow超前n个节点，fast到达链表末尾时，slow就是倒数第n个结点while(n){fast = fast->next;//题目自己保证右边的fast不会为空n--;}while(fast){fast = fast->next;pre = slow;slow = slow->next;}pre->next = slow->next;delete slow;ListNode* ans = dummy->next;delete dummy;return ans;}
};