Leecode刷题之路第19天之删除链表的倒数第N个结点

server/2024/10/18 9:30:03/

题目出处

19-删除链表的倒数第N个结点-题目出处

题目描述

在这里插入图片描述

个人解法

思路：

todo

代码示例：（Java）

todo

复杂度分析

todo

官方解法

19-删除链表的倒数第N个结点-官方解法

前言

在这里插入图片描述

方法1：计算链表长度

思路：

在这里插入图片描述

代码示例：（Java）

public class Solution1 {@Datapublic static class ListNode {int val;ListNode next;ListNode() {}ListNode(int val) {this.val = val;}ListNode(int val, ListNode next) {this.val = val;this.next = next;}}public ListNode removeNthFromEnd(ListNode head, int n) {ListNode dummy = new ListNode(0, head);int length = getLength(head);ListNode cur = dummy;for (int i = 1; i < length - n + 1; ++i) {cur = cur.next;}cur.next = cur.next.next;ListNode ans = dummy.next;return ans;}public int getLength(ListNode head) {int length = 0;while (head != null) {++length;head = head.next;}return length;}}

复杂度分析

时间复杂度：O(L)，其中 L 是链表的长度。
空间复杂度：O(1)。

方法2:栈

思路：

我们也可以在遍历链表的同时将所有节点依次入栈。根据栈「先进后出」的原则，我们弹出栈的第 n 个节点就是需要删除的节点，并且目前栈顶的节点就是待删除节点的前驱节点。这样一来，删除操作就变得十分方便了。

在这里插入图片描述

代码示例：（Java）

public class Solution2 {@Datapublic static class ListNode {int val;ListNode next;ListNode() {}ListNode(int val) {this.val = val;}ListNode(int val, ListNode next) {this.val = val;this.next = next;}}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;}}

复杂度分析

时间复杂度：O(L)，其中 L 是链表的长度。
空间复杂度：O(L)，其中 L 是链表的长度。主要为栈的开销。

方法3:双指针

思路：

在这里插入图片描述

代码示例：（Java）

public class Solution3 {@Datapublic static class ListNode {int val;ListNode next;ListNode() {}ListNode(int val) {this.val = val;}ListNode(int val, ListNode next) {this.val = val;this.next = next;}}public ListNode removeNthFromEnd(ListNode head, int n) {ListNode dummy = new ListNode(0, head);ListNode first = head;ListNode second = dummy;for (int i = 0; i < n; ++i) {first = first.next;}while (first != null) {first = first.next;second = second.next;}second.next = second.next.next;ListNode ans = dummy.next;return ans;}}