LeetCode 19. Remove Nth Node From End of List

Given a linked list, remove the nth node from the end of list and return its head.

For example,
Given linked list: 1->2->3->4->5, and n = 2. After removing the second node from the end, the linked list becomes 1->2->3->5.

Note:Given n will always be valid.
Try to do this in one pass.

大致意思就是给定一个链表，删除链表中倒数第n个节点，只允许我们遍历链表一次。
本科学习数据结构时老师留过类似的作业题，此题与其的区别是要删除倒数第n个节点而不是查找，所以我们要查找到倒数第n+1个节点，令p和q间的距离为n+1，同时由于本题需要自己手动附加头节点，所以初始时可以令p指向附加头节点，q指向正数第n个节点，同时平移指针p和指针q，当指针q指向链表最后一个节点时，指针p恰好指向链表倒数第n+1个节点，即倒数第n个节点的前驱节点。该算法的时间复杂度为O(n)，且只需遍历链表一次；空间复杂度为O(1).
代码如下：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
     
        ListNode first = new ListNode(0);  // 附加头结点
        first.next = head;
        ListNode p = first;
        ListNode q = first.next;
        for(int i = 1; i < n; i++)  // 将q从第1个节点移动到第n个结点
            q = q.next;
        while(q.next != null)
        {
            p = p.next;
            q = q.next;
        }
        p.next = p.next.next;
        return first.next;
    }
}