LeetCode 练习——19. 删除链表的倒数第 N 个结点
文章目录
- 1.题目描述
- 2.思路
-
- 2.1 代码
- 2.2 测试结果
- 3.总结
1.题目描述
删除链表的倒数第 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]2.思路
2.1 代码
删除链表节点的方法是让删除节点的前一个节点的 next 指向待删除节点的 next 即可，因此本题需要先找到待删除节点的前一个节点。
删除链表倒数第 n 个节点，这里使用一个 fast 指针先走 n 步，然后再使用一个 slow 指针和 fast 同时往前走，当fast指针走到最后一个节点时候停止，此时 slow 指针指向的节点即倒数第 n 个节点的前一个节点，此时使用 slow.next = slow.next.next 即可将倒数第 n 个节点删除。需要注意的是，当 fast 指针先前进 n 步之后 fast 指针指向 null ，则表示当前需要删除头节点，即 n 等于链表长度，此时返回 head.next。步骤如下：
- 先让 fast 指针先前进 n 步；
- fast 指针和 slow 指针同时前进，直到 fast 指针的 next 指向 null 为止；
- 让 slow 指针的 next 指向 slow.next.next
代码如下：
class Solution { public ListNode removeNthFromEnd(ListNode head, int n) { if (head.next == null) { return null; } ListNode fast = head; ListNode slow = head; while (n > 0) { fast = fast.next; n--; } if (fast == null) { return head.next; } while (fast.next != null) { fast = fast.next; slow = slow.next; } slow.next = slow.next.next; return head; }}2.2 测试结果
通过测试
3.总结
- 删除链表节点只需让待删除节点的前一个节点的 next 指向待删除节点的 next 节点即可
- 使用 fast 指针先前进 n 步，然后使用 slow 指针和 fast 指针同时前进的方式找到待删除节点的前一个节点
- 当 fast 指针先前进 n 步之后 fast 指向 null ，表示此时需要删除头节点，直接返回头节点的 next 即可
