https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/

点击查看【bilibili】

题目

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

示例

  1. 给定一个链表: 1->2->3->4->5, 和 n = 2.
  3. 当删除了倒数第二个节点后，链表变为 1->2->3->5.

19. 删除链表的倒数第N个节点 Remove Nth Node From End of List - 图1
说明：
给定的 n 保证是有效的。
进阶：
你能尝试使用一趟扫描实现吗？

解答

删除节点

  1. 创建两个指针

image.png
移动n2，2个节点
image.png
移动最终结果：n1指向的节点就是要删掉的节点
image.png
由于我们没有办法直接删除4节点，需要3指向5，也就是4的前一个节点，指向4的后一个节点
image.png

解决方法

方法1：让n2多走一位
image.png
image.png
方法2：让n2走到节点最后的位置，而不是空值
image.png

考虑边界问题

如果链表只有一个节点，如何把第一个节点空出来，返回一个空
image.png

解决方法

在第一个节点前，创建dummy节点，作为第0个节点
image.png

答案

/**
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */
var removeNthFromEnd = function(head, n) {
    let dummy = new ListNode()
    dummy.next = head //dummy指向链表的头部
    let n1 = dummy
    let n2 = dummy
    // n2 移动n个位置
    for(let i=0;i<=n;i++){
        n2 = n2.next
    }
    // 当n2移动到链表结尾，n1指向目标节点的前一个节点
    while(n2 !== null) {
        n1 = n1.next
        n2 = n2.next
    }

    n1.next = n1.next.next //指向目标节点后一个节点
    return dummy.next
};