leetcode:19.删除链表的倒数第N个节点

题目描述：

给定一个链表，删除链表的倒数第 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)$O(n)，n为链表的节点个数，这里只进行了一次遍历。