双向链表删除节点时间复杂度_leetcode 19 删除链表的倒数第N个节点(c++)
第一种方法：两次遍历(12ms),超过10%。
第二种方法：一次遍历( 4ms)，击败93%
leetcode的耗时好像个位数的毫秒之间并不准确，原题链接：
力扣leetcode-cn.com
### 题目
给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
示例：
给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后，链表变为 1->2->3->5.
说明：
给定的 n 保证是有效的。
### 思路
首先先将倒数的第N个节点找出正序时候的位置，很明显可以得出倒数的第N个节点在正序中的位置是l+1-N(其中l是链表的总长度)，题目已经说过了N是有效数字,所以就不用判断N是否有效了。
下一步就开始删除了，因为是单向链表，所以为了方便，另外定义一个ahead来保存指针遍历到的节点的前向节点。当删除头节点的时候，直接返回头结点的next节点就可以了，当删除第N个节点的时候，将第N-1个节点的next指针指向N+1（当为第N个节点为最后一个节点时，N+1是null,也可以正确运行），然后删除第N个节点，所以也没有问题。
但是这是一个两次遍历了，而且还存在内存泄漏。
时间复杂度：O(L)，算法对链表进行了两次遍历，首先计算了链表的长度l，其次找到第l-n+1个结点。
空间复杂度：O(1)。
### code
/**
### 思路
此方法为一次遍历，利用双指针，p1、p2最开始都是指向头结点的，但是因为要删除的是倒数第N个节点，所以第一个指针p1先向前走N-1步，第二个指针p2才开始向前遍历，这样当指针p1->next指向NULL的时候，p2指针就正好指向要删除的节点，然后删除掉p2所指的这个节点就可以了，。
删除方法有点low，因为没有存储下来p2的前面一个节点，所以就将p2->next->val赋给了p2->val，然后删除掉p2->next，所以严格来说是删除了p2->next，也就是说严格来说是删除了倒数第N+1个节点。
时间复杂度：O(L)，该算法对链表进行了一次遍历。
空间复杂度：O(1)。
### code
/**