关于网站开发的学校,上海传媒公司总裁李闪闪,dj网站建设,电子商务网站域名注册方法删除链表的倒数第 N 个结点
给你一个链表#xff0c;删除链表的倒数第 n 个结点#xff0c;并且返回链表的头结点。
示例 1#xff1a; 输入#xff1a;head [1,2,3,4,5], n 2 输出#xff1a;[1,2,3,5]
解题思路
1、使用快慢指针找到要删除节点的前一个节点。2、删…删除链表的倒数第 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)只需要使用常数级别的额外空间。
