讨论/算法和数据结构/删除链表的倒数第N个节点/
删除链表的倒数第N个节点

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

示例:

给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后,链表变为 1->2->3->5.
说明:

给定的 n 保证是有效的。

进阶:

你能尝试使用一趟扫描实现吗?

展开讨论

解法1:

/**
 * 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 node = head;
    const arrNodes = [];
    while(true) {
        if(node === null) {
            const length = arrNodes.length;
            if(length === n ) 
                head = head.next;
            else 
                arrNodes[length-n-1].next=arrNodes[length-n+1];
            break;
        }       
        arrNodes.push(node);
        node = node.next;
    }
    return head;
};

解法2:

/**
 * 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 node = head;
    let length = 0;
    while(true) {
        if(node === null) {
            break;
        }       
        node = node.next;
        length++;
    }
    node = head;
    if(n === length) return head.next;
    for(let i = 0; i< length - n -1; i++) {
        node=node.next;
    }
    node.next=node.next.next
    return head;
};

解法3 by glowd

var removeNthFromEnd = function(head, n) {
    let store = head;
    let p = head;
    let i = 0;
    while(p) {
        if(i>n) store = store.next;
        p = p.next;
        i++;
    }
    if(i === n) return store.next;
    store.next = store.next.next;
    return head;

};
展开全部 4 讨论