图解LeetCode——19. 删除链表的倒数第 N 个结点

一、题目

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

二、示例

2.1> 示例 1：

【输入】head = [1,2,3,4,5], n = 2

【输出】[1,2,3,5]

2.2> 示例 2：

【输入】head = [1], n = 1

【输出】[]

2.3> 示例 3：

【输入】head = [1,2], n = 1

【输出】[1]

提示：

• 链表中结点的数目为 sz
• 1 <= sz <= 30
• 0 <= Node.val <= 100
• 1 <= n <= sz

进阶：

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

三、解题思路

根据题目描述，我们要去删除倒数第N个节点，那么由于该链表的单向性，我们可以通过遍历先计算整个链表中的节点的个数，比如一共有6个节点，那么如果要删除倒数第3个节点的话，我们其实就是要删除从头结点开始计算的第4个节点，这样就可以完成题意了。

但是在题目给出的进阶部分，它提出我们能否尝试使用一趟扫描实现吗？那么上面的解题思路就不适合这种要求了。我们可以采用双指针（p1，p2）的方式，即：还是以一共有6个节点，我们要删除倒数第3个节点为例。为了方便起见，我们可以创建一个虚拟节点，然后放到整个链表的头部，这样加入要删除倒数第6个节点，即：头结点的话，我们也更方便操作。

那么由于要删除倒数第3个节点，我们可以先让p2向后执行3步，这样，p1与p2步数之差就是3步了。然后我们同时让p1和p2都一步一步的向链表的末尾移动，当p2指向了链表中的最后一个节点的时候，我们就可以停止p1与p2的移动操作了。那么此时我们会发现p1指向的节点正好是倒数第4个节点，而p1.next就是我们要删除的节点。那么删除操作就非常容易了，即：p1.next = p1.next.next；

以上就是解题思路了，为了便于理解，我们以输入head = [1,2,3,4,5,6], n = 3为例，看一下具体的操作过程。具体操作流程，请见下图所示：

四、代码实现

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode temp = new ListNode(-1);
        temp.next = head;
        ListNode p1 = temp, p2 = temp;
        while(n-- > 0) {
            p2 = p2.next;
        }
        while (p2.next != null) {
            p1 = p1.next;
            p2 = p2.next;
        }
        p1.next = p1.next.next;
        return temp.next;
    }
}
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */

今天的文章内容就这些了：

写作不易，笔者几个小时甚至数天完成的一篇文章，只愿换来您几秒钟的 点赞 & 分享 。

更多技术干货，欢迎大家关注公众号“爪哇缪斯” ~ \(^o^)/ ~ 「干货分享，每天更新」