刷网站排名 优帮云网图搜索识别
删除链表的倒数第 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)，只需要使用常数级别的额外空间。