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

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

示例:

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

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

给定的 n 保证是有效的。

进阶:

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

共 4 个回复
func removeNthFromEnd(head *ListNode, n int) *ListNode {

    store := head
    i := 0
    p := head
    for p != nil {

        if(i>n) {
            store = store.Next
        }

		p = p.Next
        i++
	}
    // 删除头节点
    if(i == n){
        return store.Next
    }
   
    store.Next=store.Next.Next
   
    return head

}
const dummy = new ListNode(0);
dummy.next = head;

let l = dummy;
let r = dummy;

let offset = n;

while (offset--) {
  r = r.next;
}

while (r.next) {
  l = l.next;
  r = r.next;
}

l.next = l.next.next;

return dummy.next;

设双指针,p1指针在p2指针的前n位,一趟扫描p2到末尾的时候,p1就指向了倒数第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;

};