同系列文章导读:【数据结构与算法】导读

所有文章均在本博客首发,其他平台同步更新

如果有更好的方法,欢迎指点,共同进步~~

有其他语言代码也可在留言区留言,谢谢

发表评论时请填写正确邮箱,以便于接收通知【推荐QQ邮箱】


  • 时间:2022-05-17
  • 题目序号:19
  • 难度:中等

问题描述

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

来源:力扣(LeetCode)

示例1

img

输入: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

解题思路

题解部分参考自代码随想录。如有侵权,请联系进行删除~~
  • 本题最先能想到的就是双重遍历(取长度,算位置,删元素)
  • 除了双循环法,还可以使用双指针进行解题
  • 还是使用虚拟头结点的方式来实现这两种方法(有虚拟头结点可以将首结点由特殊变为一般位置)

双重遍历

  • 首先通过第一次循环,获得当前链表的长度size
  • 然后运用数学计算的方式,得到倒数第n个结点正数时的索引(size - n)
  • 得到指定元素正数位置后,找到前一个结点,断开其连接即可完成删除操作

双指针法

  1. 首先让fast和slow指针都指向虚拟头结点

  1. 先让fast往前走n+1个位置(和slow相隔n个结点)

  1. slow和fast同时后移,直到fast为null

这时fast已经到链表尾部了,而slow和它相隔n个结点

也就是从后往前,slow指向的位置是倒数第n个元素的前一个结点

  1. slow.next = slow.next.next,断开连接,完成删除操作

代码实现

双重遍历

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dum = new ListNode(-1, head);
        int size = 0;
        while(head != null){        // 获取链表大小
            size++;
            head = head.next;
        }
        ListNode p = dum;
        for(int i = 0; i < size - n; i++){        // 查找被删结点的前结点
            p = p.next;
        }
        p.next = p.next.next;        // 删除元素
        ListNode res = dum.next;    // 返回头结点
        return res;
    }
}

双指针法

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dum = new ListNode(-1, head);
        ListNode slow = dum, fast = dum;
        while(n-- >= 0){     // 让fast和slow之间相距n个结点
            fast = fast.next;
        }
        while(fast != null){        // 将slow指向被删除的上一个结点
            slow = slow.next;
            fast = fast.next;
        }
        slow.next = slow.next.next;
        return dum.next;
    }
}

总结

  • 使用虚拟头结点可以将首结点由特殊位置转变为一般位置,简化操作。(否则需要对首结点做特殊处理)
  • 涉及到指针操作时,都可以考虑考虑双指针法,配合图解更容易理解一些
最后修改:2022 年 05 月 17 日
如果觉得我的文章对你有用,请随意赞赏