题目描述：
给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
示例：
给定一个链表: 1->2->3->4->5, 和 n = 2. 当删除了倒数第二个节点后，链表变为 1->2->3->5.
说明：
给定的 n 保证是有效的。
题目难度：中等
分析：
题目已经给出了链表类，此链表比较简单，是个单链表，并且还有一个构造方法。链表是数据结构中比较常见的一种，优点就是增删比较快，对于这题来说，题目的要求是删除倒数第N个节点，所以我们只需要找到倒数第N个节点在哪，然后把它的前一个节点指向它的后一个节点，即可删除此节点。那么问题就是我们究竟怎么才能准确的找到这个节点呢？其实我们只需要用两个指针即可，让他们之间保持恒定的N个距离，然后把其中一个移动到最后的null节点，那么另一个就在倒数第N+1的节点位置了。
代码如下：
/** * 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) { // 定义一个空节点作为结果，并且指向head节点 ListNode res = new ListNode(0); res.next = head; // 用两个指针分别指向res节点 ListNode p = res; ListNode q = res; // 利用循环让p指针移动N+1次，因为此时的p是指向res的，所以移动N+1次就是正数第N个节点（下标从0开始） // 这样的话p和q之间就间隔了N个节点 for (int i = 0; i < n + 1; i ++) { p = p.next; } // 让p指针指向链表的最后一位的下一位（就是指向null） // 因为p和q是同时移动的，那么此时的q指针就指向了倒数第N+1位（下标从1开始） while (p != null) { p = p.next; q = q.next; } // 这时只要把q指针的next位指向下下一位就可以跳过这个倒数第N位啦。 q.next = q.next.next; return res.next; } }
这里借用一下leetcode官方题解的图，让大家更容易理解。
总结：
时间复杂度为O ( n ) ，n为链表的节点个数，这里只进行了一次遍历。
