购物网站支付页面制作,有什么免费的wordpress,京东商城网站特色,中山网站快照优化公司文章目录 题目方法一#xff1a;节点加入集合找索引方法二#xff1a;直接计算长度,然后找出要删除的节点的前一个节点方法三#xff1a;栈方法四#xff1a;前后双指针 题目 这题的关键在与两个点 一定要设置一个哑结点#xff0c;防止删除第一个元素时#xff0c;导致空… 文章目录 题目方法一节点加入集合找索引方法二直接计算长度,然后找出要删除的节点的前一个节点方法三栈方法四前后双指针 题目 这题的关键在与两个点 一定要设置一个哑结点防止删除第一个元素时导致空指针异常 删除链表的元素其实就等价于找到这个元素的前一个元素 方法一节点加入集合找索引 先将ListNode存到list 然后直接找到要删除节点的前一个节点即可node.next node.next.next public static ListNode removeNthFromEnd(ListNode head, int n) {ListNode pre new ListNode(0, head);//创建哑结点 解决要删除的元素时第一个 空指针异常ListListNode list new ArrayList();//将链表节点存到listListNode h pre;while(h ! null){list.add(h);h h.next;}//找到要删除的数的前一个节点ListNode node list.get(list.size()-1-(n-1)-1);node.next node.next.next;return pre.next;}方法二直接计算长度,然后找出要删除的节点的前一个节点 public static ListNode removeNthFromEnd(ListNode head, int n) {//得出链表的长度int length getLength(head);ListNode pre new ListNode(0, head);//创建哑结点 解决要删除的元素时第一个 空指针异常//倒数n个 为 length - n 1int l length - n 1;ListNode cur pre;for (int i 1; i l ; i ) {cur cur.next;}cur.next cur.next.next;return pre.next;}//计算链表长度public static int getLength(ListNode head){int len 0;while(head !null){len ;head head.next;}return len;}方法三栈
依次入栈直到null 然后要删除的元素 n 多少 就弹出对少元素 弹出的元素就是要删除的元素 例如找n1 倒数第一个 则直接弹出栈顶元素删除即可
此时当弹出n个数之后 此时栈顶其实就是要删除的数的前一个数了也满足将删除链表元素转换为找到要删除元素的前一个元素 public static ListNode removeNthFromEnd(ListNode head, int n) {ListNode dummy new ListNode(0, head);//哑结点 删除第一个元素空指针异常DequeListNode stack new LinkedListListNode(); //栈ListNode cur dummy;while (cur ! null) {stack.push(cur);cur cur.next;}for(int i 0; in ; i){stack.pop();//弹出对应的栈顶元素 最后弹出的元素就是要删除的元素}//此时要删除的前一个元素时栈顶元素ListNode pre stack.peek();pre.next pre.next.next;return dummy.next;}方法四前后双指针
关键在于指针的设置fast起始就比slow快一个节点然后按照n fast往前移动个位置然后再slow和fast同步移动直到fast走到null此时slow指向的就是要删除元素的前一个位置也就是为什么开始就要fast比slow快一个位置的原因不然等fast走到null了结果slow指向的要删除的元素这样不太好执行node.next node.next.next操作因为删除链表的元素其实就等价于找到这个元素的前一个元素 public static ListNode removeNthFromEnd(ListNode head, int n) {ListNode dummy new ListNode(0, head);//哑结点 防止删除第一个元素空指针异常ListNode fir head;ListNode bef dummy;//先指针领先 bef n 个位置for(int i0;in;i){fir fir.next;}//当 fir遍历到链表的末尾时 bef的下一个节点就是我们需要删除的节点。while(fir !null){fir fir.next;bef bef.next;}bef.next bef.next.next;return dummy.next;}
