百度权4必应权4,日IP8000!查看详情 !世界已冷酷至极, 让我们携手前行。
自助收录

19. 删除链表的倒数第 N 个结点(解法一:单调栈)

算法刷题2年前 (2023)更新 江南白衣
463 0 0
19. 删除链表的倒数第 N 个结点(解法一:单调栈)

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

19. 删除链表的倒数第 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]
分析:
题目中提到“倒数”这个关键词,很容易想到可以使用栈这种数据结构,我们可以在遍历链表的同时将所有结点依次入栈。根据栈「先进后出」的原则,我们弹出栈的第 n个节点就是需要删除的节点,并且目前栈顶的结点就是待删除节点的前驱节点。
复杂度分析
时间复杂度:O(L)O(L),其中 LL 是链表的长度。
空间复杂度:O(L)O(L),其中 LL 是链表的长度。主要为栈的开销。

package com.codernav.demo.leetcode.linkedlist.removeElements;

import com.codernav.demo.common.ListNode;

import java.util.Stack;

/**
 * @title 19. 删除链表的倒数第 N 个结点(栈)
 * @Description 给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。
 * @Author 开发者导航
 * @website https://www.codernav.com
 * @date 2023/3/4
 */
public class Q_19_2 {
    public static void main(String[] args) {
        ListNode node5 = new ListNode(5, null);
        ListNode node4 = new ListNode(4, node5);
        ListNode node3 = new ListNode(3, node4);
        ListNode node2 = new ListNode(2, node3);
        ListNode node1 = new ListNode(1, node2);
        // 双指针
        ListNode head = removeNthFromEnd(node1, 2);
        System.out.println(head);
    }

    public static ListNode removeNthFromEnd(ListNode head, int n) {
        // 虚拟结点
        ListNode dummyNode = new ListNode(0);
        dummyNode.next = head;

        // 将结点放入栈(包括虚拟结点)
        Stack<ListNode> stack = new Stack<>();
        ListNode curr = dummyNode;
        while (curr != null) {
            stack.push(curr);
            curr = curr.next;
        }

        // 移除最后n个元素
        for (int i = 0; i < n; i++) {
            stack.pop();
        }
        // 找到要移除元素的前驱元素
        ListNode prev = stack.peek();
        // 删除结点
        prev.next = prev.next.next;

        return dummyNode.next;
    }
}
© 版权声明

相关文章

开发者导航新手教程

暂无评论

暂无评论...