Description（876. 链表的中间结点）

给定一个头结点为 head 的非空单链表，返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。

示例 1：

输入：[1,2,3,4,5]
输出：此列表中的结点 3 (序列化形式：[3,4,5])
返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。
注意，我们返回了一个 ListNode 类型的对象 ans，这样：
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.

示例 2：

输入：[1,2,3,4,5,6]
输出：此列表中的结点 4 (序列化形式：[4,5,6])
由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。

提示：

给定链表的结点数介于 1 和 100 之间。

Solution

学到了一个很巧妙的办法——快慢指针。

通过两个指针，慢指针一次加一，快指针一次加二，那么在快指针到末尾的时候，慢指针就对应着链表中的中间位置，直接输入慢指针即可。

var middleNode = function(head) {
    slow = fast = head;
    while (fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
};

Description（19. 删除链表的倒数第 N 个结点）

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

示例 1：

输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

示例 2：

输入：head = [1], n = 1
输出：[]

示例 3：

输入：head = [1,2], n = 1
输出：[1]

提示：

链表中结点的数目为 sz
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz

进阶：你能尝试使用一趟扫描实现吗？

Solution

本体也应用了快慢指针，因为要删除链表的倒数第n个节点，那么假设一个慢指针，一个快指针，快指针=慢指针+n，那么循环到最后时，当快指针走到链表末尾时，慢指针指向的节点就是要删除的节点，这时直接指向下下个节点就相当于删除该节点。

考虑到特殊情况，如果快指针不为空，真实存在，那么以上成立；如果为空，就表示只有一个节点，那么直接返回头节点的下一个节点即可。

var removeNthFromEnd = function(head, n) {
    let slow = head, fast = head;
    for(let i = 0; i < n; i++) {
        fast = fast.next;
    }
    if(!fast)
        return head.next;
    while(fast.next != null) {
        fast = fast.next;
        slow = slow.next;
    }
    slow.next = slow.next.next;
    return head;
};