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

结点"/>

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

题目链接

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

题目描述

给你一个链表，删除链表的倒数第 n 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]

提示：

• 链表中结点的数目为 s z sz sz
• 1 ≤ s z ≤ 30 1 \leq sz \leq 30 1≤sz≤30
• 0 ≤ N o d e . v a l ≤ 100 0 \leq Node.val \leq 100 0≤Node.val≤100
• 1 ≤ n ≤ s z 1 \leq n \leq sz 1≤n≤sz

解法一：栈

用一个栈 s t k stk stk，先将所有链表节点入栈。

然后再弹出 n n n 个节点，此时栈顶节点就是 倒数第 n + 1 n + 1 n+1 个节点。

我们直接让 倒数第 n + 1 n + 1 n+1 个节点 指向 倒数第 n − 1 n - 1 n−1 个节点，这样就把 倒数第 n n n 个节点删除了。

注意： 由于可能弹出全部的节点，栈可能为空，所以我们要对边界条件做特殊处理。

时间复杂度： O ( n ) O(n) O(n)

C++代码：

class Solution {
public:ListNode* removeNthFromEnd(ListNode* head, int n) {stack<ListNode*> stk;ListNode* cur = head;while(cur){stk.push(cur);cur = cur->next;}for(int i = 0;i < n;i++) stk.pop();if(stk.empty()) return head->next;ListNode* pre = stk.top();pre->next = pre->next->next;return head;}
};

解法二：双指针

我们开始让 f a s t , s l o w fast ,slow fast,slow 分别指向 链表头节点 h e a d head head；

接着让 f a s t fast fast 先走 n n n 步，此时 f a s t fast fast 和 s l o w slow slow 之间就间隔 n n n 个节点。

接着再让 f a s t , s l o w fast,slow fast,slow 往后移动，当 f a s t fast fast 为空的时候说明此时 s l o w slow slow 就是 倒数第 n n n 个节点。

我们在删除这个 倒数第 n n n 个节点即可。

时间复杂度： O ( n ) O(n) O(n)

C++代码：

class Solution {
public:ListNode* removeNthFromEnd(ListNode* head, int n) {ListNode* dummy = new ListNode(-1);ListNode* pre = dummy;pre->next = head;ListNode* fast = head , *slow = head;while(n--){fast = fast->next;}while(fast){pre = pre->next;slow = slow->next;fast = fast->next;}pre->next = pre->next->next;return dummy->next;return head;}
};