删除链表倒数第N个结点

删除链表倒数第N个结点

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

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

题解

这个题目不看进阶的话很简单，就是单纯的链表的操作方法

/**
 * 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 *p,*q;
      p=head;
      q=head;
      int count = 0;
      while(p!=nullptr) // 计算节点个数
      {
        q=p;
        p=p->next;
        count++;
      }  
      int target = count - n;
      if(target == 0) //考虑是否为头结点
      {
        ListNode* newhead = head->next;
        delete head;
        return newhead;
      }
      else
      {
        p=head;
        for(int i=0;i<target;i++){ //找到要删除的节点，以及上一个节点
            q=p;
            p=p->next;
        }
        q->next=p->next;
        delete p;
      }
     return head; 
    }
};

然后就是进阶方法，只扫描一次，那么根据前几个题，循环如果想降低时间复杂度的话，一般都是双指针，那么这个题的关键就是在于，要先知道链表的长度，才能查询要删除的节点，这两个怎么合并成一个操作呢？

看示例一，需要删除倒数第二个，那么我们就需要找到倒数第三个结点，抛开这个示例，如果链表长度为 len ,删掉的是倒数第 n 个，那么从正方向来看，就是要找到第 len-n 个，因为我们需要的是要删除节点的前一个。

// 1 2 3 4 5
while(n>=0&&p!=nullptr)  //n+1步，找到第n+2个
{
    p=p->next;
    n--;
}
while(p!=nullptr)   //len-n-1步，找到第len-n个
{
    p=p->next;
    q=q->next;
}

但是，分析示例2，我们就会发现，在上述程序中，第一个while循环，会出现 nullptr->next ，这肯定是错误的，那么应该怎么做呢，可以引入虚节点。

// Head 1 2 3 4 5
ListNode* Head = new ListNode(0);//虚节点
Head->next = head;
ListNode* p=Head;
ListNode* q=Head;
while(n>=0&&p!=nullptr)  //n+1步，找到第n+1个
{
    p=p->next;
    n--;
}
while(p!=nullptr)  //len-n步，找到第len-n个
{
    p=p->next;
    q=q->next;
}
ListNode* temp = q->next;
q->next=temp->next;
delete temp;
return Head->next;

在这个代码中，示例二在第一个while循环中，p成为nullptr，q会保持Head不变，解决了上面的问题，并且正确。

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* Head = new ListNode(0);
        Head->next = head;
        ListNode* p = Head;
        ListNode* q = Head;
        while (n >= 0 && p != nullptr) // n+1步，找到第n+1个
        {
            p = p->next;
            n--;
        }
        while (p != nullptr) // len-n步，找到第len-n个
        {
            p = p->next;
            q = q->next;
        }
        ListNode* temp = q->next;
        q->next = temp->next;
        delete temp;
        return Head->next;
    }
};