A

ASCE1885

V1

2022/07/30阅读:10主题:默认主题

【萌新解题】删除链表的倒数第 N 个结点

关于我:微信公众号:面试官问,原创高质量面试题,始于面试题,但不止于面试题。【萌新解题】系列文章试图从新人的角度去看待和解决力扣题目,本题是力扣第 19 题 删除链表的倒数第 N 个结点:https://leetcode.cn/problems/remove-nth-node-from-end-of-list。

题目描述

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

前置知识点

很多链表相关的问题都可以使用双指针法来解决。双指针法可以根据两个指针不同的移动方式细分成两种不同的方法:

  • 前后双指针:即一个指针在链表中提前朝着指向下一个节点的指针移动若干步,然后再同时移动第二个指针
  • 快慢双指针:即两个指针在链表中移动的速度不一样,通常是快的指针朝着指向下一个节点的指针一次移动两步,慢的指针一次只移动一步。

解题说明

本题是前后双指针的典型应用,通常为了删除一个节点,应该找到被删除节点的前一个节点,然后把该节点的 next 指针指向它下一个节点的下一个节点,这样下一个节点没有被其他节点引用,也就相当于被删除了。 要删除链表倒数第 n 个节点,根据链表删除节点的特性,我们并不是直接找到要删除的这个节点,而是要找到倒数第 n+1 个节点,然后通过修改倒数第 n+1 个节点的指针实现删除倒数第 n 个节点。

代码如下所示:

class Solution {
    /**
     * 通常为了删除一个节点,应该找到被删除节点的前一个节点,然后把该节点的next指针指向它下一个节点的下一个节点,这样下一个节点没有被其他节点引用,也就相当于被删除了。 
     * 要删除链表倒数第 n 个节点,根据链表删除节点的特性,我们并不是直接找到要删除的这个节点
     * 而是要找到倒数第 n+1 个节点,然后通过修改倒数第 n+1 个节点的指针实现删除倒数第 n 个节点
     */

    public ListNode removeNthFromEnd(ListNode head, int n) {
        // 引入哨兵节点,避免处理例如输入的链表为空,或者被删除的节点是原始链表的头节点等边界问题
        ListNode dummy = new ListNode();
        dummy.next = head;

        // 前指针
        ListNode first = head;

        // 后指针
        ListNode second = dummy;

        // 前指针先移动到 n-1 的位置
        for (int i=0; i<n; ++i) {
            first = first.next;
        }

        // 前后双指针同时移动,直到前指针到达链表尾部
        while (first != null) {
            first = first.next;
            second = second.next;
        }

        // 此时后指针已经指向倒数第 n+1 个节点,删除它的下一个节点也就是倒数第 n 个节点即可
        second.next = second.next.next;

        return dummy.next;        
    }
}

复杂度分析

  • 时间复杂度:O(n),其中 n 是链表的长度
  • 空间复杂度:O(1),没有使用额外的存储空间

分类:

后端

标签:

后端

作者介绍

A
ASCE1885
V1