【LeetCode】19. 删除链表的倒数第 N 个结点(中等)——代码随想录算法训练营Day04

发布时间:2024年01月13日

题目链接:19. 删除链表的倒数第 N 个结点

题目描述

给你一个链表,删除链表的倒数第?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

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

文章讲解:代码随想录

视频讲解:链表遍历学清楚! | LeetCode:19.删除链表倒数第N个节点_哔哩哔哩_bilibili

题解1:暴力法

思路:先遍历一遍链表得出链表总长度,再通过计算删除链表倒数第 n 个节点。

/**
 * 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) {
    // 第1次遍历,得出链表元素的个数
    let size = 0;
    let cur = head;
    while (cur) {
        size++;
        cur = cur.next;
    }


    // 链表中元素的位置为0,1,2,...,size -1
    // 倒数第1个元素位置为 size -1,倒数第2个为 size - 2,倒数第 n 个为 size - n
    // 要取 size - n - 1 位置的元素,需要取头指针向后移动 size - n - 1 位
    const vHead = new ListNode(0, head); // 虚拟头节点
    cur = vHead;
    for (let i = 0; i < size - n; i++) {
        cur = cur.next;
    }
    // 删除 cur 位置的下一个元素
    cur.next = cur.next ? cur.next.next : null;
    return vHead.next;
};

分析:遍历了2次链表,时间复杂度为 O(n),空间复杂度为 O(1)。

题解2:快慢指针

思路:可以使用快慢指针的思想来解这道题。初始化时让快指针和慢指针都指向头节点,先让快指针前进 n 步,再让快指针和慢指针同时前进,当快指针到达链表结束时,慢指针就指向了倒数第 n 个节点。

/**
 * 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 vHead = new ListNode(0, head); // 虚拟头节点
    let slow = fast = vHead; // 初始化快慢指针
    // 快指针先前进 n + 1 步
    for (let i = 0; i < n + 1; i++) {
        fast = fast.next;
    }
    // 快慢指针同步移动,当快指针移动到链表末尾时,慢指针指向倒数第 n 个元素的上一个元素
    while (fast) {
        fast = fast.next;
        slow = slow.next;
    }
    // 删除慢指针位置的下一个元素
    slow.next = slow.next.next;
    return vHead.next;
};

分析:使用了快慢指针法,只对链表进行了一次遍历,时间复杂度为 O(n),空间复杂度为 O(1)。

收获

学会了一种非常巧妙的快慢指针思路,虽然单链表无法像数组一样可以通过下标索引直接找到对应元素,但利用快慢指针之间的差值寻找倒数元素这种方法还是很精妙的。

文章来源:https://blog.csdn.net/m0_57521762/article/details/135570765
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。