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

题意：

解题思路：

思路：
    1. 头部添加虚拟节点；
    2. 快慢指针同时指向虚拟节点；
    3. 快指针先走n步；
    4. 快慢指针同时移动，直到快指针下一个节点为空；
    5. 慢指针的下一个节点指向下下一个节点；
    6. 最后返回虚拟节点的下一个节点即可；

PHP代码实现：

/**
 * Definition for a singly-linked list.
 * class ListNode {
 *     public $val = 0;
 *     public $next = null;
 *     function __construct($val) { $this->val = $val; }
 * }
 */
class Solution {
    function removeNthFromEnd($head, $n) {
        $dummy = new ListNode(0); // 首先新建一个链表的结点
        $dummy->next = $head;//令这个结点指向head
        $fast = $dummy;
        $slow = $dummy;
        for ($i = 0; $i < $n; $i++) {
            $fast = $fast->next;
        }
        //当快指针指向最后空节点的时候，慢指针刚好指向倒数第n个节点
        while ($fast->next != null) {
            $fast = $fast->next;
            $slow = $slow->next;
        }
        $slow->next = $slow->next->next;
        return $dummy->next;
    }
}

GO代码实现：

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func removeNthFromEnd(head *ListNode, n int) *ListNode {
    dummy := new(ListNode)
    dummy.Next = head
    fast, slow := dummy, dummy
    for i := 0; i <= n; i++ {
        fast = fast.Next
    }
    for fast != nil {
        fast = fast.Next
        slow = slow.Next
    }
    slow.Next = slow.Next.Next
    return dummy.Next
}