leetcode19：删除链表倒数第 n 个结点

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

示例：

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

说明：

给定的 n 保证是有效的。

进阶：

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

附leetcode地址：leetcode

快慢指针法
快指针先走n个节点，然后快慢指针一起，知道快指针走到null,这时慢指针指向n-1，将慢指针指向快指针。

解法：快慢指针

解题思路： 需要删除链表中的倒数第 n 个节点，我们需要知道的就是倒数第 n+1 个节点，然后删除删除倒数第 n+1 节点的后继节点即可

步骤：

使用 2 个指针：

fast 快指针提前走 n+1 步
slow 指针指向当前距离 fast 倒数第 n 个节点，初始为 head

然后， fast 、 slow 同步向前走，直到 fast.next 为 null

此时，fast 为最后一个节点，slow 就是倒数第 n+1 个节点，此时问题就变更为删除链表中的 slow 的后继节点

但存在一个问题，当链表长度为 n 时，fast 是前进不到 n+1 个节点位置的，所以此时有两种解决思路：

创建一个头节点 preHead ，设置 preHead.next = head ，这样就可以解决以上问题，删除倒数第 n 个节点后，返回的 preHead.next 即可
另外一种是，fast 快指针提前走 n 步后，判断 fast.next 是否为 null ，即 fast 是否是最后一个节点，如果是，则 head 为倒数第 n 个节点，此时问题可以简化为删除头节点；如果不是， fast = fast.next ，fast 再前进一步，slow 为倒数第 n+1 个节点，也解决了以上问题。

解决方案一：添加 preHead 节点

const removeNthFromEnd = function(head, n) {
    let preHead = new ListNode(0)
    preHead.next = head
    let fast = preHead, slow = preHead
    // 快先走 n+1 步
    while(n--) {
        fast = fast.next
    }
    // fast、slow 一起前进
    while(fast && fast.next) {
        fast = fast.next
        slow = slow.next
    }
    slow.next = slow.next.next
    return preHead.next
};

解决方案二：单独处理倒数第 n 节点

const removeNthFromEnd = function(head, n) {
    let fast = head, slow = head
    // 快先走 n 步
    while(--n) {
        fast = fast.next
    }
    if(!fast.next) return head.next
    fast = fast.next
    // fast、slow 一起前进
    while(fast && fast.next) {
        fast = fast.next
        slow = slow.next
    }
    slow.next = slow.next.next
    return head
};

时间复杂度：O(n)

空间复杂度：O(1)

leetcode

瓶子君，不是很明白这里

slow.next = slow.next.next
return head

改变的是 slow，为什么返回的是 head

瓶子君，不是很明白这里
slow.next = slow.next.next
return head
改变的是 slow，为什么返回的是 head

因为题目要求在删除了指定节点后，需要返回的是链表的头结点。所以返回的是head。

new ListNode(0) 这个是什么

var removeNthFromEnd = function(head, n) {
    const dump = new ListNode(-1)

    dump.next = head

    let fast = dump
    let slow = dump

    while (n--) {
        fast = fast.next
    }

    while (fast.next) {
        fast = fast.next
        slow = slow.next
    }

    slow.next = slow.next.next

    return dump.next
};

注释写的先走的步数是不是有问题？

第一种解法： n-- 先走 n 步,
第二种解法: --n 先走n-1步

var removeNthFromEnd = function (head, n) {
    // 哨兵节点
    let dump = new ListNode();
    dump.next = head;
    // 快慢指针
    let fast = slow =  dump;

    // 快指针先走n步
    for (let i = 0; i < n; i++) {
        fast = fast.next;
    }
    // 快指针走到最后，当前slow为倒数第n+1个节点
    while(fast && fast.next) {
        fast = fast.next;
        slow = slow.next;
    }
    slow.next = slow.next.next;
    return dump.next;
};

借用数组存放链表节点通过数组下标进行删除
var removeNthFromEnd = function(head, n) {
if(head === null) return null;
var arr = [];
var p = head;
while(p){
arr.push(p);
p = p.next;
}
var pos = arr.length-n;
if(pos===0) return head.next;
arr[pos-1].next = arr[pos].next;

for(let i=pos+1;i<=arr.length-1;i++){
    arr[i-1]=arr[i];
}

return head;

};

快慢指针：
var removeNthFromEnd = function(head, n) {
if(head === null) return head;
var slow = head,fast = head,count=n+1;//找到倒数第n+1个节点
//通过删除倒数第n+1个节点的后继节点来实现删除倒数第n个节点

//快指针先走n+1步 再快慢指针同步走 当快指针指向null 慢指针指向倒数第n+1个节点
while(fast && count>0){
    fast = fast.next;
    count--;
}
//当倒数第n个节点为head 快指针走到第n步即为null
if(fast===null && count!==0){
    head = head.next;
    return head;
}
while(fast){
    fast = fast.next;
    slow = slow.next;
}

slow.next = slow.next.next;
return head;

};

题目地址(19. 删除链表的倒数第 N 个节点)

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

题目描述

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

示例：

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

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

给定的 n 保证是有效的。

进阶：

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

前置知识

链表
双指针

公司

阿里
百度
腾讯
字节

思路

这里我们可以使用双指针算法，不妨设为指针 A 和指针 B。指针 A 先移动 n 次，指针 B 再开始移动。当 A 到达 null 的时候，指针 B 的位置正好是倒数第 n。这个时候将 B 的指针指向 B 的下下个指针即可完成删除工作。

算法：

设置虚拟节点 dummyHead 指向 head（简化判断，使得头结点不需要特殊判断）
设定双指针 p 和 q，初始都指向虚拟节点 dummyHead
移动 q，直到 p 与 q 之间相隔的元素个数为 n
同时移动 p 与 q，直到 q 指向的为 NULL
将 p 的下一个节点指向下下个节点

(图片来自： https://github.com/MisterBooo/LeetCodeAnimation)

关键点解析

链表这种数据结构的特点和使用
使用双指针
使用一个 dummyHead 简化操作

代码

代码支持: JS, Java，CPP

Javascript Code:

/**
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */
var removeNthFromEnd = function (head, n) {
  let i = -1;
  const noop = {
    next: null,
  };

  const dummyHead = new ListNode(); // 增加一个dummyHead 简化操作
  dummyHead.next = head;

  let currentP1 = dummyHead;
  let currentP2 = dummyHead;

  while (currentP1) {
    if (i === n) {
      currentP2 = currentP2.next;
    }

    if (i !== n) {
      i++;
    }

    currentP1 = currentP1.next;
  }

  currentP2.next = ((currentP2 || noop).next || noop).next;

  return dummyHead.next;
};

Java Code:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        TreeNode dummy = new TreeNode(0);
        dummy.next = head;
        TreeNode first = dummy;
        TreeNode second = dummy;

        if (int i=0; i<=n; i++) {
            first = first.next;
        }

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

        second.next = second.next.next;

        return dummy.next;
    }
}

CPP Code:

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode *p = head, *q = head;
        while (n--) q = q->next;
        if (!q) {
            head = head->next;
            delete p;
            return head;
        }
        while (q->next) p = p->next, q = q->next;
        q = p->next;
        p->next = q->next;
        delete q;
        return head;
    }
};

复杂度分析

时间复杂度：$O(N)$
空间复杂度：$O(1)$

大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。目前已经 37K star 啦。
大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。

我自己用了递归回溯的方式，也是只扫描了一遍，虽然没有 快慢指针 巧妙，但大家也可以参考一下

const removeNthFromEnd = (head: Node | undefined, n: number) => {
    if (n <= 0) return head;
    if (!head) return head;
    let result: Node | undefined = head;
    const fn = (prev: Node | undefined, node: Node | undefined): number => {
        if (!node) return 0;
        const deep = fn(node, node.next) + 1;
        if (deep === n) {
            if (!prev) {
                // 删除的head
                result = node.next;
            } else {
                const nextNode = node.next;
                prev.next = nextNode;
            }
        }
        return deep;
    };
    fn(undefined, head);
    return result;
};

注释写的先走的步数是不是有问题？

第一种解法： n-- 先走 n 步, 第二种解法: --n 先走n-1步

你理解为slow和fast闭区间内的步数就可以了

Navigation Menu

Repository navigation

leetcode19：删除链表倒数第 n 个结点 #16

解法：快慢指针

题目地址(19. 删除链表的倒数第 N 个节点)

题目描述

前置知识

公司

思路

关键点解析

代码

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

leetcode19：删除链表倒数第 n 个结点 #16

Description

Activity

taoeer commented on Apr 14, 2020

sisterAn commented on Apr 14, 2020

解法：快慢指针

plane-hjh commented on May 7, 2020

gyt95 commented on Jul 7, 2020

hundren commented on Aug 7, 2020

qianlongo commented on Aug 15, 2020

zsg857981535 commented on Sep 14, 2020

AnranS commented on Nov 17, 2020

Anoi1018 commented on Jan 28, 2021

Anoi1018 commented on Jan 28, 2021

azl397985856 commented on Mar 3, 2021

题目地址(19. 删除链表的倒数第 N 个节点)

题目描述

前置知识

公司

思路

关键点解析

代码

JohnApache commented on Apr 26, 2021

jxtprivate commented on Mar 22, 2023

Metadata

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Issue actions