今日题目
给定一个链表，删除链表的倒数第 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]
提示：
链表中结点的数目为 sz 1 <= sz <= 30 0 <= Node.val <= 100 1 <= n <= sz
进阶：尝试使用一趟扫描实现吗？
思路一
由于链表只有头节点暴露，所以不清楚到底链表长度是多少，也就不清楚第n个节点在哪，
所以我们可以使用可以保留顺序索引的容器存储，这样就可以根据索引直接删掉倒数第n个节点
public ListNode removeNthFromEnd(ListNode head, int n) { ListNode cuur = head; List<ListNode> nodelist = new ArrayList<>(); while (cuur != null) { nodelist.add(cuur); cuur = cuur.next; } int len = nodelist.size(); //只有一个元素时，返回空 if (len == 1 && n == 1) { return null; } //删除掉倒数第n个，也就是正数第一个head节点 if (len == n) { return nodelist.get(1); } //其他情况删除节点，返回head nodelist.get(len - n - 1).next = nodelist.get(len - n).next; return head; }
执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：37.7 MB, 在所有 Java 提交中击败了5.03%的用户
思路二
另一种思路就是遍历两遍，第一遍找到总长度，第二遍根据总长度和n找到需要删除的节点
public ListNode removeNthFromEnd2(ListNode head, int n) { ListNode cuur = head; int length = 1; //第一遍计算出总长度 while (cuur.next != null) { length++; cuur = cuur.next; } if (n == length) { head = head.next; } else { cuur = head; //第二遍删除第n个节点 for (int i = 1; i < length - n; i++) { cuur = cuur.next; } cuur.next = cuur.next.next; } return head; }
执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：36.4 MB, 在所有 Java 提交中击败了58.58%的用户
思路三
利用快慢指针，由于是删除倒数第n个，让快指针先走n - 1步，然后慢指针再从头出发，与快指针同时前进。当快指针走到结尾的时候，slow.next就是要删除的节点。 执行slow.next = slow.next.next即可。小技巧还是通过创建哨兵节点来简化头节点的处理方式。
public ListNode removeNthFromEnd(ListNode head, int n) { //新建哨兵节点，方便处理头节点 ListNode pre = new ListNode(); pre.next = head; ListNode fast = pre, slow = pre; for (int i = 0; i < n; i++){ fast = fast.next; } while (fast.next != null){ fast = fast.next; slow = slow.next; } //删除slow.next slow.next = slow.next.next; return pre.next; }
执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：36.3 MB, 在所有 Java 提交中击败了76.05%的用户
小结
这道题重点要学会快慢指针的思想，其他解法相对来说不是重点只作为了解即可，算法考察的更多是快慢指针的思想，需要掌握其原理。
