【链表】Leetcode 19. 删除链表的倒数第 N 个结点【中等】

删除链表的倒数第 N 个结点

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

示例 1：

输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

解题思路

• 1、使用快慢指针找到要删除节点的前一个节点。
• 2、删除目标节点。

具体步骤

• 初始化两个指针 first 和 second，都指向链表的头节点。
• 将 first 移动到第 n 个节点。
• 然后同时移动 first 和 second，直到 first 指向链表末尾。
• 此时 second 的下一个节点就是要删除的节点，
• 将 second.next 指向 second.next.next

java实现

public class RemoveNthFromEnd {public ListNode removeNthFromEnd(ListNode head, int n) {ListNode dummy = new ListNode(0);dummy.next = head;ListNode first = dummy;ListNode second = dummy;// 将 first 移动到第 n 个节点for (int i = 0; i <= n; i++) {first = first.next;}// 同时移动 first 和 second，直到 first 指向末尾while (first != null) {first = first.next;second = second.next;}// 删除倒数第 n 个节点second.next = second.next.next;return dummy.next;}public static void main(String[] args) {// 构造链表 1 -> 2 -> 3 -> 4 -> 5ListNode head = new ListNode(1);head.next = new ListNode(2);head.next.next = new ListNode(3);head.next.next.next = new ListNode(4);head.next.next.next.next = new ListNode(5);int n = 2;// 调用 removeNthFromEnd 方法删除倒数第 n 个节点RemoveNthFromEnd solution = new RemoveNthFromEnd();ListNode result = solution.removeNthFromEnd(head, n);// 打印删除后的链表while (result != null) {System.out.print(result.val + " ");result = result.next;}// 输出：1 -> 2 -> 3 -> 5}
}
class ListNode {int val;ListNode next;ListNode(int x) {val = x;next = null;}
}

时间空间复杂度

• 时间复杂度：O(n)，其中 n 是链表的长度，需要遍历一次链表。
• 空间复杂度：O(1)，只需要使用常数级别的额外空间。