删除链表的倒数第 N 个结点（leetcode）

19. 删除链表的倒数第 N 个结点（leetcode）

难度中等1961

给你一个链表，删除链表的倒数第 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

原题链接：19. 删除链表的倒数第 N 个结点

---

思路：运用双指针原理：

1.先定义两个指针q、p，并指向起点，p先移动N次。

2.q，p同时移动，直到p指尾节点。

3.此时，q指向的节点为倒数第N个节点。

以下为图解：

 

在编码过程中，可能遇到的问题

        头节点的特判问题，对头结点这个特殊位置要进行特判，我们可以运用哑节点dummy解决特判问题。

/* 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 *dummy=new ListNode (-1),*cur=dummy;
         dummy->next = head;
         ListNode *p=dummy->next,*q=dummy->next;
         int s=0;
         while(snext;} //p先移动N次
         
         for(;q&&p;p=p->next) {
             cur=cur->next;
             q=q->next;
         } 
         cur->next=q->next;
         auto r=dummy->next;
         delete dummy;//释放内存空间
         return r;
     }
 };

以上代码还有可以优化的空间：

删除节点的思路：

1.知道删除节点，和与被删除节点的前一个节点。

2.知道被删节点的前一个节点，然后用q->next=q->next->next 删除该删除的节点。


        我们可以把cur这个变量可以去掉。

我们可以将q=dummy->next变成q=dummy，其他不变，多遍历了一个节点，所以结果就变成倒数第k+1个节点。

所以我们就可以直接用q->next=q->next->next将倒数第k个节点删除。

 代码：

/**
  * 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 *dummy=new ListNode (-1);
         dummy->next = head;
         ListNode *p=dummy->next,*q=dummy;
         int s=0;
         while(snext;} 
         for(;q&&p;p=p->next) {
             q=q->next;
         }
         q->next=q->next->next; //删除倒数第k个节点
         ListNode *r=dummy->next;
         delete dummy;  //释放内存
         return r;//返回节点
 ​
     }
 };