解析思路

leetcode 中等难度，题目描述点击这里。

第一眼看过去很多人都能想到两次编辑即可。第一次遍历获取链表长度，第二次遍历走到对应位置即可。

但是题目进阶描述中要求用一次遍历来实现。

通常涉及到链表位置问题的我们都可以考虑用快慢指针来实现。题目删除倒数第 n 个节点，那么我们可以:

  • 定义 pq 两个指针
  • 先让 q 走 n 步，等到 q 走到最后一个节点时，p 刚好在倒数第 n-1 个节点上，删除 p 的下一个节点即可
  • 考虑特殊情况，n 等于链表长度，这种情况下当 q 走 n 步时，刚好为 null,为 null 时直接返回 p 的下一个节点即可,返回 p.next
  • 让 q 走到最后一个节点，再删除 p 的下一个节点
  • 返回 head

代码

public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode p = head, q = head;
    //先将p,q的距离差拉到n,这样当q在结尾时，刚好p在倒数第n+1个位置上，删除下一个位置即可
    while ((n--) > 0) {
        q = q.next;
    }
    //考虑特殊情况，当n等于链表长度时，需要删除第一个元素
    if (q == null) {
        return p.next;
    }
    //让q走到结尾
    while (q.next != null) {
        q = q.next;
        p = p.next;
    }
    //删除p的下一个节点
    p.next = p.next.next;
    return head;
}