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

1、参考资料

https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/

2、题目要求

题目描述

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

示例：

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

进阶：

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

3、代码思路

这道题的思路和寻找链表倒数第 N 个节点的思路相似，使用双指针可以通过一趟遍历完成

不同的是寻找链表倒数第 N 个节点需要定位至倒数第 K 个节点，而单链表的删除需要定位至待删除节点的前一个节点，即倒数第 N+1 个节点那么问题就来了，我如果想要删除链表的首节点怎么办？首节点可是没有前一个节点的呀，这时候头结点(dummyHead)就派上用场了，我们在原链表的基础上定义一个头结点 dummyHead，dummyHead 指向原链表的首节点(head)我们定义两个指针：front 指向链表前部，behind 指向链表后部，我们目标是当 behind 指向 null 的时候，front 指向倒数第 N+1 个节点，此时通过 front.next =f ront.next.next 即可删除倒数第 N 个节点

---

边界条件的确定

因为我们需要定位至倒数第 N+1 个节点，所以 front 与 behind 始终相差 N+1 个节点

就拿下面的例子来说明，链表为 1 --> 2 --> 3 --> 4 --> 5，我们需要删除倒数第 2 个节点

1 --> 2 --> 3 --> 4 --> 5 --> null

首先我们在链表前面加一个 dummyHead，让 front 指向 dummyHead，让 behind 指向 head

dummyHead --> 1 --> 2 --> 3 --> 4 --> 5 --> null ^ ^ | | front behind

behind 向后移动两步，即初始化时 behind 指向 head，然后向后移动 N 步

dummyHead --> 1 --> 2 --> 3 --> 4 --> 5 --> null ^ ^ | | front behind

front 和 behind 一起向后移动，直至 behind 为空

dummyHead --> 1 --> 2 --> 3 --> 4 --> 5 --> null ^ ^ | | front behind

front.next =f ront.next.next 删除倒数第 2 个节点

dummyHead --> 1 --> 2 --> 3 --> 5 --> null ^ ^ | | front behind

4、代码实现

代码

static class Solution { public ListNode removeNthFromEnd(ListNode head, int n) { // DummyHead ListNode dummyHead = new ListNode(0); dummyHead.next = head; ListNode front = dummyHead; // 初始化时 front 指向 dummyHead ListNode behind = head; // 初始化时 front 指向 head // behind 向后移动 n 步，保证 front 和 behind 相差 n+1 步 int count = 0; for (; count < n && behind != null; count++) { behind = behind.next; } // 如果输入的 n 大于链表长度，则直接返回原链表 if (count < n) { return head; } // front 和 bbehind 一起后移 while (behind != null) { behind = behind.next; front = front.next; } // 删除倒数第 n 个节点 front.next = front.next.next; // 返回新链表的首节点 return dummyHead.next; } } static class ListNode { int val; ListNode next; ListNode(int x) { val = x; } }