建网站流程的费用,dede网站,网站付费推广方式,企业网站建设合作协议书一、题目
给你一个链表#xff0c;删除链表的倒数第 n 个结点#xff0c;并且返回链表的头结点。 示例 1#xff1a; 输入#xff1a;head [1,2,3,4,5], n 2
输出#xff1a;[1,2,3,5]示例 2#xff1a;
输入#xff1a;head [1], n 1
输出#xff1a;[]示例 3删除链表的倒数第 n 个结点并且返回链表的头结点。 示例 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]二、思路 1.容易想到的思路就是先遍历一遍链表统计长度倒数第n个节点就是正数的第len - n 1个节点。要删除该节点我们要找到len - n的节点即可删除。 2.经典思路删除倒数第n个节点让fast移动n步然后让fast和slow同时移动直到fast指向链表末尾。删掉slow所指向的节点就可以了。为了统一头节点和其他节点的删除操作使用虚拟头节点。
三、代码 暴力解
public class Test {public static void main(String[] args) {Scanner sc new Scanner(System.in);System.out.println(请输入链表的元素输入非数字结束);ListNode head new ListNode(sc.nextInt());ListNode current head;while (sc.hasNextInt()) {ListNode node new ListNode(sc.nextInt());current.next node;current current.next;}ListNode listNode removeNthFromEnd(head, 2);//打印链表current listNode;while (current ! null) {System.out.print(current.val );current current.next;}}public static ListNode removeNthFromEnd(ListNode head, int n) {//暴力法//先统计链表长度找到该节点的前一个节点即可,倒数第n个节点是正数的第(len-n1)个节点int len 0;ListNode cur head;while (cur ! null) {len;cur cur.next;}//如果只有一个元素if(len 1){return null;}// 如果需要删除头节点if (len - n 0) {return head.next;}cur head;//找到第len-n1个节点的前一个节点for (int i 1; i len - n; i) {cur cur.next;}cur.next cur.next.next;return head;}
} 双指针法 class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {//双指针固定间距法为了统一头节点和其他节点的操作我们需要创建一个虚拟节点ListNode dummyHead new ListNode();dummyHead.next head;//快慢指针指向虚拟头节点ListNode fastIndex dummyHead;ListNode slowIndex dummyHead;//先让快指针走n1 步再同时移动这里为什么是n1 呢//因为我们在删除节点的时候要找到前一个节点//将区间扩大到n1那么当快指针为空时慢指针才能到达被删除节点的前一个节点for(int i 0; i n;i) {fastIndex fastIndex.next;}while(fastIndex ! null) { //快慢指针同时移动fastIndex fastIndex.next;slowIndex slowIndex.next;}// 检查 slowIndex.next 是否为 null以避免空指针异常if (slowIndex.next ! null) {slowIndex.next slowIndex.next.next;}return dummyHead.next;}
}
