题目
本题为leetcode探索初级算法中链表章节的一题
给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
示例：
给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后，链表变为 1->2->3->5.
说明：
给定的 n 保证是有效的。
进阶：
你能尝试使用一趟扫描实现吗？
作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xn2925/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
我的解法
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode lengthHead = head;
int length = 1;
while(lengthHead.next != null){
length++;
lengthHead = lengthHead.next;
}
if(n == length){
head = head.next;
return head;
}
ListNode removePreHead = head;
while(length != n + 1){
length--;
removePreHead = removePreHead.next;
}
removePreHead.next = removePreHead.next.next;
return head;
}
}
思路就是第一次循环得到长度，知道长度后删除倒数第n个就容易了。总共循环了两次，未能达到进阶要求。
官方解法
解法一：
复杂度分析：
时间复杂度：O(L)O(L)，该算法对列表进行了两次遍历，首先计算了列表的长度 LL 其次找到第 (L - n)(L−n) 个结点。 操作执行了 2L-n2L−n 步，时间复杂度为 O(L)O(L)。
空间复杂度：O(1)O(1)，我们只用了常量级的额外空间。
跟我的思路大致相同，官方中使用了哑结点作为辅助，有效的避免极端情况，而我都是通过提前判断来实现的。
解法二：
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode first = dummy;
ListNode second = dummy;
// Advances first pointer so that the gap between first and second is n nodes apart
for (int i = 1; i <= n + 1; i++) {
first = first.next;
}
// Move first to the end, maintaining the gap
while (first != null) {
first = first.next;
second = second.next;
}
second.next = second.next.next;
return dummy.next;
}
复杂度分析:
时间复杂度：O(L)O(L)，该算法对含有 LL 个结点的列表进行了一次遍历。因此时间复杂度为 O(L)O(L)。
空间复杂度：O(1)O(1)，我们只用了常量级的额外空间。
解法二使用两个指针先让第一个指针A移动n个距离，在两个指针一起移动，直到指针A移动到结尾。非常巧妙，学习了！