mx52jing

Appearance

Return to top
On this page

19-删除链表的倒数第N个结点

标签：链表 双指针

题目信息

题目地址： 19.删除链表的倒数第N个结点

题目内容：

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

示例1：
    输入：head = [1,2,3,4,5], n = 2
    输出：[1,2,3,5]

示例 2：
    输入：head = [1], n = 1
    输出：[]

示例 3：
    输入：head = [1,2], n = 1
    输出：[1]

提示：
    链表中结点的数目为 sz
    1 <= sz <= 30
    0 <= Node.val <= 100
    1 <= n <= sz

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

示例1图片如下：

题解

解法一

思路：

要删除倒数第n个节点，就需要找到倒数第n+1个节点，假设n = 1，也就是删除倒数第1个节点，那么就要找到它前面的节点，也就是倒数第2个节点

定义虚拟头节点dummyHead，默认指向head，定义两个指针slow和fast，初始值都是dummyHead，然后让fast先向后走n步，然后fast和slow同步向右移动

直到fast.next为null的时候，此时slow.next刚好指向了要删除的节点，然后进行删除即可

看下图会更好理解一些

leetcode-19-remove-nth-node-from-end

代码实现：

javascript
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */
var removeNthFromEnd = function(head, n) {
    const dummyHead = new ListNode(0, head)
    let slowPointer = dummyHead
    let fastPointer = dummyHead
    while(n--) { // fastPointer先走n步
       // n不合法，大于链表的size
       if(fastPointer.next === null) {
            return null
       }
       fastPointer = fastPointer.next 
    }
    while(fastPointer.next !== null) {
        fastPointer = fastPointer.next 
        slowPointer = slowPointer.next
    }
    slowPointer.next = slowPointer.next.next
    return dummyHead.next
};