LeetCode_LinkedList_19. Remove Nth Node From End of List 删除链表的倒数第 N 个结点（C++）【双指针，一次遍历】

目录

​​一，题目描述​​

​​英文描述​​

​​中文描述​​

​​二，解题思路​​

​​三，AC代码​​

​​C++​​

​​四，解题过程​​

​​第一博​​

一，题目描述

英文描述

Given the head of a linked list, remove the nth node from the end of the list and return its head.

Example 1:

Example 2:

Example 3:

Constraints:

The number of nodes in the list is sz.
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz

Follow up: Could you do this in one pass?

中文描述

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

进阶：你能尝试使用一趟扫描实现吗？

示例 1：

示例 2：

示例 3：

提示：

链表中结点的数目为 sz
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz

来源：力扣（LeetCode）
链接：​​​https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list​​ 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

二，解题思路

链表问题中一个难点就是计数。因为没有相应的索引或者属性来标明当前位置，所以必须通过遍历来确定链表节点数量和位置，然而针对本题，有一个简单的技巧来判断位置，即双指针法。

与之前判断循环链表的双指针法不同，这里的两个指针移速相同，即每轮只向前移动一步，但是两个指针的间距不同，在本题中为n。（这里假设n=2） 

提到链表删除节点，必须要想起前驱节点，只有知道待删除节点的前驱节点，才能顺利完成删除操作。 

由于删除的节点可能是头节点，为了简化程序，这里设计一个虚拟头节点h，h->next指向head。

p->next = p->next->next，返回h->next即可

三，AC代码

C++

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* h = new ListNode;
        h->next = head;
        ListNode* p = h, * q = head;
        for(int i = 0; i < n; i++) q = q->next;
        while(q != nullptr) {
            p = p->next;
            q = q->next;
        }
        p->next = p->next->next;
        return h->next;
    }
};

四，解题过程

第一博

一发入魂