【算法面试必刷Java版九】删除链表的倒数第n个节点

盲目刷题，浪费大量时间，博主这里推荐一个面试必刷算法题库，刷完足够面试了。传送门：牛客网面试必刷TOP101

🏄🏻作者简介：CSDN博客专家，华为云云享专家，阿里云专家博主，疯狂coding的普通码农一枚

    

🚴🏻‍♂️个人主页：莫逸风

    

👨🏻‍💻专栏题目地址👉🏻牛客网面试必刷TOP101👈🏻

    

🇨🇳喜欢文章欢迎大家👍🏻点赞🙏🏻关注⭐️收藏📄评论↗️转发

题目：删除链表的倒数第n个节点

描述：

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

例如：

给出的链表为: 1→2→3→4→5, n= 2.

删除了链表的倒数第 nn 个节点之后,链表变为1→2→3→5.

数据范围： 链表长度 0≤n≤1000，链表中任意节点的值满足0≤val≤100

要求：空间复杂度 O(1)，时间复杂度 O(n)

备注：

题目保证 nn 一定是有效的

思路：双指针

本题其实和上一个题目是相同的，我们只需要找到倒数第k个节点，然后多加一个指针用于标记倒数第k个节点的前一个节点。

找倒数第k个节点：

定义cur指针指向第k个元素，result指向队头，然后同步遍历，当cur走到队尾，result即为倒数第k个元素。

代码：

public ListNode removeNthFromEnd(ListNode head, int n) {
    // write code here
    ListNode pre = new ListNode(-1);
    pre.next = head;
    head = pre;
    ListNode cur = head.next;
    ListNode next = head.next;
    while (n-- > 0) {
        if (cur == null) {
            return null;
        }
        next = next.next;
    }
    while (next != null) {
        pre = pre.next;
        next = next.next;
        cur = cur.next;
    }
    if (cur!= null){
        pre.next = cur.next;
    }
    return head.next;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

推荐牛客网面试必刷算法题库，刷完足够面试了。传送门：牛客网面试必刷TOP101