看兔子如何删除单链表的倒数第 N 个结点
一、题目描述
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
image.png
示例 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]
提示：
- 链表中结点的数目为
sz 1 <= sz <= 300 <= Node.val <= 1001 <= n <= sz
二、思路分析
先从最简单的思路说起，想要知道倒数第几个节点的位置，首先要知道链表长度信息。
但是从题目信息，我们只得知这是一个单链表，并不知道它的长度信息。
这时候就可以考虑先遍历一遍链表的节点，统计一下链表的长度，然后再计算出节点在链表中的位置，这时候就用这个节点的前驱节点指向它的后继节点。
但是这里面有一个点要注意一下，如果删除的是头节点该怎么处理
代码实现
class Solution { public ListNode removeNthFromEnd(ListNode head, int n) { // 计算链表长度 int length = 0; ListNode temp = head; while (temp != null) { ++length; temp = temp.next; } // 增加前置节点，防止删除第一个元素 ListNode ans = new ListNode(0, head); temp = ans; // 计算出要删除节点在链表中的位置 for (int i = 1; i < length - n + 1; i++) { temp = temp.next; } temp.next = temp.next.next; return ans.next; } }
从代码实现中，我们可以看出空间复杂度为O(1)，时间复杂度为O(n)
那么是不是还有更加优雅的方法呢？
小伙伴们，优雅的方法肯定是有的，就看你怎么理解这个了……
假设倒数第K个节点就是尾节点，那么我们只要把指针指向它的前驱节点即可，不需要在进行第二次扫描处理。
那么如何制造出倒数第K个节点就是尾节点的错觉呢？这就不的不请出两只小白兔了，假如在一条笔直笔直的小路上，我们让两只速度一样的小白兔赛跑，让其中的一只先跑K米，然后在再让另一只小白兔起跑……
那么请问一下，当先跑的那只小白兔到达终点的时候，另一个小白兔离终点还有多少米？
没错，这就是这题的关键思路，两只兔子解法~~~
class Solution { public ListNode removeNthFromEnd(ListNode head, int n) { if (head.next == null) { return null; } ListNode first = head; ListNode second = head; while (n > 0) { first = first.next; --n; } if (first == null) { return head.next; } while (first.next != null) { first = first.next; second = second.next; } second.next = second.next.next; return head; } }
从代码实现中，我们可以看出空间复杂度为O(1)，时间复杂度为O(n)
三、总结
关于链表的问题，基本上就是通过遍历链表解决问题，一次遍历不够就两次。此时我们可以使用空间换时间的策略，可以优先考虑是否能用多个指针，每个指针代表一次遍历，从而减少遍历的次数，提高查询效率。
