当前位置：首页 > news >正文

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

news 2025/6/30 22:16:13

题目：
在这里插入图片描述
地址：https://leetcode.cn/problems/remove-nth-node-from-end-of-list/

方法一：
在这里插入图片描述

方法二：
在这里插入图片描述

代码：

package com.zy.leetcode.LeetCode_19;/*** @Author: zy* @Date: 2024-12-25-13:01* @Description: 删除链表的倒数第N 个结点*/
public class ListNode_19 {private int val;private ListNode_19 next;public ListNode_19(int val, ListNode_19 next) {this.val = val;this.next = next;}public ListNode_19() {}public ListNode_19 removeNthFromEnd(ListNode_19 head, int n) {//添加哨兵ListNode_19 s = new ListNode_19(-1, head);recursion(s, n);return s.next;}public ListNode_19 removeNthFromEnd2(ListNode_19 head, int n) {//添加哨兵ListNode_19 s = new ListNode_19(-1, head);ListNode_19 p1 = s;ListNode_19 p2 = s;// 先让p2 先走 n 步for (int i = 0; i < n; i++) {p2 = p2.next;}// 然后让p1 和 p2 同时前进，直到 p2 为 nullwhile (p2 != null) {p1 = p1.next;p2 = p2.next;}// 删除 p1 所指的节点if (p1 != null && p1.next != null) {p1.next = p1.next.next;} else {p1 = null;}return s.next;}/*** 递归方式* 根据输入的节点，删除倒数numK 的值** @param node 节点* @param numK 倒数第几* @return*/private int recursion(ListNode_19 node, int numK) {if (node == null) {return 0;}//返回下一节点的位置int nth = recursion(node.next, numK);//进行判断if (nth == numK) {// 删除该节点if (node != null || node.next != null) {node.next = node.next.next;} else {node = null;return 0;}}return nth + 1;}public static void main(String[] args) {ListNode_19 node1 = new ListNode_19(1, null);//        ListNode_19 node2 = new ListNode_19(2, null);//        ListNode_19 node3 = new ListNode_19(3, null);//        ListNode_19 node4 = new ListNode_19(4, null);//        ListNode_19 node5 = new ListNode_19(5, null);//        node1.next = node2;//        node2.next = node3;//        node3.next = node4;//        node4.next = node5;while (node1 != null) {System.out.println(node1.val);node1 = node1.next;}System.out.println("------------");ListNode_19 result = new ListNode_19().removeNthFromEnd(node1, 1);ListNode_19 result1 = new ListNode_19().removeNthFromEnd(node1, 1);while (result1 != null) {System.out.print(result1.val + " -> ");result1 = result1.next;}}
}