LeetCode(C++)刷题计划：19

admin管理员组

文章数量:1794759

LeetCode(C++)刷题计划：19

19-删除链表的倒数第N个节点

@Author：CSU张扬 @Email：csuzhangyang@gmail or csuzhangyang@qq

CategoryDifficultyPass rateTagsCompanies

algorithms	Medium	36.08%	linked-list / two-pointers	Unknown

1. 题目

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

示例： 给定一个链表: 1->2->3->4->5, 和 n = 2. 当删除了倒数第二个节点后，链表变为 1->2->3->5.

说明：

给定的 n 保证是有效的。

进阶：

你能尝试使用一趟扫描实现吗？

来源：力扣（LeetCode） 链接：leetcode-cn/problems/remove-nth-node-from-end-of-list/

2. 解法：双指针法

如何找到链表的倒数第 n n n 个节点？

定义两个指针 l1，l2，均指向头结点。

先让 l1 向右移动 n - 1 次。

然后再同时向右移动 l1 和 l2，等到 l1 移动到尾节点时， l2 此时指向倒数第 n 个节点。

需要注意的是，我们目的是要 删除 倒数第 n 个节点，所以我们要找到倒数第 n + 1 个节点。也就是步骤 2 中，l1 总共应该向右移动 n 次。

接下来，思考这么一个问题。 假如我们的链表长度为 n n n，而我们要删除倒数第 n n n 个元素（也就是第一个元素），这时会有什么问题呢？

答案很明显，我们无法找到倒数第 n + 1 n+1 n+1 个元素，也就是第0个元素，但是我们没有第0个元素，这时就无法删除第一个元素了。

有的人可能会说，那我们直接对这种情况特殊处理就好啦。 但是，需要注意的是，我们的复杂度要求是 只遍历一遍链表 ，也就是我们先前并不知道链表的长度，也就无法判断是否是这种情况。

在这里，我们给出两种解决办法。

2.1 解法一

向头结点前增加一个结点，也就是添加了第0个元素。

注意一个问题。 最后返回的是 h->next，开头我们定义了 l1 = l2 = h, l1->next = head，即：h->next = head，那么能不能返回 head 呢？ 答案是不能。 在删除的是第一个元素的情况下结果会出错，例如：

输入：[1,2,3,4,5] 5 输出：[1,2,3,4,5] 预期结果：[2,3,4,5]

因为我们的目的是删除该头结点，我们并没有对 head 这个头结点有任何操作，那么最后返回 head 的话就必定会有头结点存在。

我们会在解法二中看到，处理删除第一个元素的情况是返回 head->next。

执行用时: 8 ms, 在所有 cpp 提交中击败了72.41%的用户 内存消耗: 8.6 MB, 在所有 cpp 提交中击败了76.23%的用户

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* removeNthFromEnd(ListNode* head, int n) { // 头结点前增加一个结点 ListNode* l1 = new ListNode(-1); l1->next = head; ListNode* l2 = l1; ListNode* h = l2; for (auto i = 0; i < n; ++ i) { l1 = l1->next; } while (l1->next) { l1 = l1->next; l2 = l2->next; } l2->next = l2->next->next; return h->next; } }; 2.1 解法二

参考【微笑永恒】

先让 l1 向右移动 n - 1 次，若此时 l1->next 为空，说明我们要删除第一个元素。直接返回 head->next 即可。

若 l1->next 不为空，l1 再向右移动一次，即共移动 n 次。

执行用时: 4 ms, 在所有 cpp 提交中击败了96.70%的用户 内存消耗: 8.4 MB, 在所有 cpp 提交中击败了90.51%的用户

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode* l1 = head; ListNode* l2 = l1; // 右移n-1次 for (auto i = 0; i < n - 1; ++ i) { l1 = l1->next; } // 判断要删除的元素是不是第一个元素 if (!l1->next) return head->next; // 应该右移n次，补上一次 l1 = l1->next; // 两个指针同时移动，直到l1到末尾 while (l1->next) { l1 = l1->next; l2 = l2->next; } // 删除该元素 l2->next = l2->next->next; return head; } };

本文标签： 计划LeetCode