力扣19.删除链表的倒数第 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

常规解法：进行两趟扫描，第一次获取长度，第二次删除节点

 1 class Solution
 2 {
 3 public:
 4     ListNode *removeNthFromEnd(ListNode *head, int n)
 5     {
 6         ListNode *p=head;
 7         int length=0;
 8         while (p)
 9         {
10             p=p->next;
11             length++;
12         }
13         p=head;
14         for (int i=0;i<length-n-1;++i){
15             p=p->next;
16         }
17         if (n==length) //删除头节点
18             head=head->next;
19         else if (n==1) //删除尾节点
20             p->next=NULL;
21         else
22             p->next=p->next->next;
23         return head;
24     }
25 };

该题还可以使用栈和双指针来实现一趟扫描。其中双指针的思路是：second指针比first指针晚n-1个节点出发，当first指针到达尾部时，second指针刚好到达倒数第n个节点处。