题目描述：

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

思路

方法1：最直观的方法，先遍历依次链表，计算链表的长度，然后再遍历依次，删除链表的倒数第n个节点
方法2：利用栈先进后出的性质，遍历链表的同时依次入栈，弹出的第n个节点就是我们要删除的节点。
方法3：双指针，先定义两个节点，second和first，先让first节点比second超前n个节点，然后依次使用两个节点对链表进行遍历，当first遍历到链表的末尾（即first为空指针）时，second恰好指向倒数第n个节点。
总结：三种方法的时间复杂度都为O(L)，其中L为链表的长度，方法1和方法3的空间复杂度都为O(1)，方法2的空间复杂度为O(L)

代码

  1. /**
  2.  * Definition for singly-linked list.
  3.  * struct ListNode {
  4.  *     int val;
  5.  *     ListNode *next;
  6.  *     ListNode() : val(0), next(nullptr) {}
  7.  *     ListNode(int x) : val(x), next(nullptr) {}
  8.  *     ListNode(int x, ListNode *next) : val(x), next(next) {}
  9.  * };
  10.  */
  11. class Solution {
  12. public:
  13.     ListNode* removeNthFromEnd(ListNode* head, int n) {
  14.         ListNode *dummy = new ListNode(0, head);
  15.         ListNode *first = head;
  16.         ListNode *second = dummy;
  18.         for(int i = 0; i < n; i++)
  19.         {
  20.             first = first->next;
  21.         }
  23.         while(first)
  24.         {
  25.             first = first->next;
  26.             second = second->next;
  27.         }
  29.         second->next = second->next->next;
  30.         ListNode *ans = dummy->next;
  32.         return ans;
  33.     }
  34. };