原题地址（中等）

方法1—快慢指针

思路

这题典型的快慢指针。先用一个快指针走n步，然后两个指针再一起走，就可以顺利找出倒数第N个数。
处理链表题的一个小技巧是建立一个虚拟头结点dummyHead，这样可以把对头结点的操作和对其他结点的操作统一起来

代码

  1. class Solution {
  2. public:
  3.     ListNode* removeNthFromEnd(ListNode* head, int n) {
  4.         ListNode* dummyHead = new ListNode(0);
  5.         dummyHead->next = head;
  6.         ListNode *p, *q, *pre;
  7.         q = dummyHead;
  8.         for(int i=0; i<n; i++)
  9.             q = q->next;
  10.         p = pre = dummyHead;
  11.         while(q) {
  12.             pre = p;
  13.             q = q->next;
  14.             p = p->next;
  15.         }
  16.         pre->next = p->next;
  17.         delete p;
  18.         return dummyHead->next;
  19.     }
  20. };

时空复杂度

时间复杂度O(L)，L为链表长度
空间复杂度O(1)