Leetcode NO.19 Remove Nth Node From End Of List 移除链表倒数第n个节点

本文主要是介绍Leetcode NO.19 Remove Nth Node From End Of List 移除链表倒数第n个节点，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1.问题描述

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

2.测试用例

示例 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]

3.提示

• 链表中结点的数目为 sz
• 1 <= sz <= 30
• 0 <= Node.val <= 100
• 1 <= n <= sz

**进阶：**你能尝试使用一趟扫描实现吗？

4.代码

1.暴力

code

 public ListNode removeNthFromEndWithForce(ListNode head, int n) {int count = 0;ListNode sentinel = new ListNode();sentinel.next = head;ListNode pre = sentinel;while (head != null) {head = head.next;count++;}for (int i = 0; i < count - n; i++) {pre = pre.next;}pre.next = pre.next.next;return sentinel.next;
}

复杂度

这种如果n比较大的比较高效
时间 O（n）
空间 O（1）

2.双重循环-栈

code

public ListNode removeNthFromEndWithStack(ListNode head, int n) {ListNode sentinel = new ListNode(-1);sentinel.next = head;// 定义栈Stack<ListNode> stack = new Stack<>();ListNode curr = sentinel;// 遍历链表，所有节点入栈while ( curr != null ){stack.push(curr);curr = curr.next;}// 依次弹栈，弹出N个for ( int i = 0; i < n; i++ ){stack.pop();}stack.peek().next = stack.peek().next.next;return sentinel.next;
}

复杂度

这种如果n比较小的比较高效
时间O（n）
空间O（n）

3.双指针

code

 public ListNode removeNthFromEndWithDoublePointer(ListNode head, int n) {ListNode sentinel = new ListNode();sentinel.next = head;ListNode rem = sentinel;ListNode end = sentinel;//1. 移动end节点到nfor (int i = 0; i < n; i++) {end = end.next;}//2. 移动rem、end节点，直到end节点指向nullwhile (end.next != null){end = end.next;rem = rem.next;}//3. 删除倒数n节点rem.next = rem.next.next;return sentinel.next;
}

复杂度

时间复杂度 O（n）
空间复杂度 O (1)

这篇关于Leetcode NO.19 Remove Nth Node From End Of List 移除链表倒数第n个节点的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---