《链表篇》---删除链表的倒数第N个节点（中等）

用户11288958

发布于 2025-01-17 14:06:52

2040

文章被收录于专栏：学习学习

题目传送门

方法一：计算链表长度（迭代）

1.计算链表长度，并且定义哑节点链接链表。 2.从哑节点开始前进length-n次。即为被删除节点的前置节点。 3.进行删除操作。 4.返回哑节点的后置节点

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        //定义一个虚拟节点，并且链接链表
        ListNode dummy = new ListNode(0,head);
        ListNode cur = dummy;
        int length = getLength(head);//获取链表长度

        //从虚拟节点开始，前进length-n次，即为被删除节点的前置节点
        for(int i = 0; i < length-n; i++){
            cur = cur.next;
        }
        cur.next = cur.next.next;
        return dummy.next;

    }

    public int getLength(ListNode head){
        int length = 0;
        while(head != null){
            length++;
            head = head.next;
        }
        return length;
    }
}

方法二：栈

在 Java 中，虽然有 Stack 类，但推荐使用 Deque（例如 LinkedList 或 ArrayDeque）来实现栈的功能。主要原因有： 1. 设计上的问题 2. 性能优势 3. 双端队列的灵活性 4. 现代化的 API
1.定义一个虚拟节点，用来找到结果链表的头结点。 2.将链表节点全部入栈，包括虚拟节点。 3.出n次栈。也就是刚好把要删除节点出栈。 4.记录栈顶元素的地址。也就是被删除节点的前置节点。 5.链接链表。将前置节点与后置节点链接起来。 6.返回虚拟节点的下一个节点。

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        Deque<ListNode> stack = new LinkedList<ListNode>();
        ListNode cur = dummy;
        while (cur != null) {
            stack.push(cur);
            cur = cur.next;
        }
        for (int i = 0; i < n; ++i) {
            stack.pop();
        }
        ListNode prev = stack.peek();
        prev.next = prev.next.next;
        ListNode ans = dummy.next;
        return ans;
    }
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-10-31，如有侵权请联系 cloudcommunity@tencent.com 删除

链表