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

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

题目描述

删除链表中倒数的第n个节点

示例：

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

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

分析

• 先遍历一次获得链表长度length
• 然后length - n 获取target, 当前target < 0 时， p->next = p->next->next

源码

/**
 * 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 root = new ListNode("head");
    root.next = head;

    let getLengthsPointer = head;

    let nums = 0;
    while(getLengthsPointer) {
        nums++;
        getLengthsPointer = getLengthsPointer.next;
    }

    let pointer = root;
    let target = nums - n;

    while(pointer) {
        target--;
        if(target < 0) {
            pointer.next =  pointer.next.next ? pointer.next.next : null;
            break;
        }
        pointer = pointer.next
    }
    return root.next;
};

进阶

一次遍历, 思想： 用双指针，第一个指针与第二个指针 相隔n, 当第一个指针到达结尾时，那么第二个指针也到了倒数第n个数的前一个了。
我们用上面 1 -> 2 -> 3 -> 4 -> 5 走一遍， n 为2

• first 指向 3 , second 指向 head， 同时向后移动
• 当first 指向到 null的时候，second 走到了 3，此时可以将second.next 指向 second.next.next

var removeNthFromEnd = function(head, n) {
    let root = new ListNode("head");
    root.next = head;

    let first = root;
    let second = root;

    for (let i = 1; i <= n + 1; i++) {
        first = first.next;
    }

    while (first != null) {
        first = first.next;
        second = second.next;
    }
    second.next = second.next.next;
    return dummy.next;


}