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

题目：

地址：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 为 null
        while (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;
        }

    }
}