删除链表的结点

题目：请编写一个函数，使其可以删除某个链表中给定的（非末尾的）节点，您将只被给予要求被删除的节点。
比如：假设该链表为 1 -> 2 -> 3 -> 4 ，给定您的为该链表中值为 3 的第三个节点，那么在调用了您的函数之后，该链表则应变成 1 -> 2 -> 4 。

分析：题中重点其实已经给出了，非末尾节点，所以我们删除节点时，只需将要删除的节点变成它的下一个节点即可。

代码：

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} node
 * @return {void} Do not return anything, modify node in-place instead.
 */
var deleteNode = function(node) {
    node.val = node.next.val
    node.next = node.next.next
};

完成日期：2018-05-23

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

分析：我们可以使用两个指针p1，p2来解决，先让它们都指向头节点，然后p2移动n次，如果p2走到末端，那么n即为链表长度，需要移除的是头节点。若没走到末端，则让p1、p2同时移动，直到p2走到末端为止。此时需要删除的节点为p1指向的节点的后一个节点，如下：

p1 -> 需要删除的节点 -> 某节点

所以只需将p1指向某节点即可。

代码：

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */
var removeNthFromEnd = function(head, n) {
    let p1 = head;
    let p2 = head;
    // p2移动n次
    for (let i = 0; i < n; i++) {
        p2 = p2.next;
    }
    // 若移动n次后，p2走到头了，n即为链表长度，需要移除的是头节点
    if (!p2) {
        return head.next;
    }
    while (p2.next) {
        p2 = p2.next;
        p1 = p1.next;
    }

    p1.next = p1.next.next;
    return head;

};

执行时间：80ms

完成日期：2018-05-23

leetcode案例

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */
var removeNthFromEnd = function(head, n) {
    let i = 0;
    let len = 0;
    let node = head;

    while (node) {
        len++;
        node = node.next;
    }

    node = head;

    if (len - n - 1 === -1) {
        head = head.next;
    } else {
        while (i < len - n - 1) {
            node = node.next;
            i++;
        }

        node.next = node.next ? node.next.next : null;
    }

    return head;
};

执行时间： 70ms

分析：先计算出链表长度。再将指针同头移动到倒数第n个节点。