technology-note/算法/leetcode/常规题/Q19. 删除链表的倒数第 N 个结点.md

---
id: "20220127"
date: "2022/01/27 10:38:05"
title: "leetcode.Q19.删除链表的倒数第N个节点"
tags: ["java", "leetcode", "链表", "快慢指针"]
index_img: https://qiniupic.fleyx.com/blog/202201271600310.jpg?imageView2/2/w/200
banner_img: https://qiniupic.fleyx.com/blog/202201271600310.jpg
categories:
  - "算法"
  - "leetcode刷题"
---


## 解析思路


leetcode 中等难度，题目描述[点击这里](https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/)。

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

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

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

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


## 代码
```java
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;
}
```