算法_链表_删除链表的倒数第N个结点

/**
 * 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
 * 输入：head = [1,2,3,4,5], n = 2
 * 输出：[1,2,3,5]
 * 示例 2：
 * 输入：head = [1], n = 1
 * 输出：[]
 * 示例 3：
 * 输入：head = [1,2], n = 1
 * 输出：[1]
 * 提示：
 * 链表中结点的数目为 sz
 * 1 <= sz <= 30
 * 0 <= Node.val <= 100
 * 1 <= n <= sz
 */
public class 删除链表的倒数第N个结点 {
    /**
     * 笨方法：
     * 1、计算单向链表中节点总数量
     * 2、计算删除节点位置
     * 3、处理特殊第一个节点
     * 4、遍历删除2-5的目标节点
     */
    public static Node.IntNode removeNthFromEnd(Node.IntNode head, int n) {
        //计算单向链表中一共有多少个node
        int len = 0;
        Node.IntNode curr = head;
        while (curr != null) {
            len += 1;
            curr = curr.next;
        }

        //计算删除元素位置
        int delNodeIndex = len - n + 1;

        //特殊处理==》001
        //当删除第一个节点的时候特殊处理
        if (1 == delNodeIndex) {
            head = head.next;
            return head;
        }

        //临时节点
        Node.IntNode tempNode = head;
        int trmpPos = 1;
        while (tempNode != null) {
            //有个问题：当n==5的时候，没有虚拟头节点，出现1==0特殊情况，需要特殊处理==》001
            if (trmpPos == delNodeIndex - 1) {//找到要删除节点的上一个节点
                //tempNode是目标节点上一个节点
                Node.IntNode delNode = tempNode.next;
                //将目标节点的下一个节点，替换当前节点
                tempNode.next = delNode.next;
                break;
            }
            //维护当前指针
            trmpPos += 1;
            //不是要删除节点的上一个节点，继续遍历下一个节点
            tempNode = tempNode.next;
        }
        return head;
    }

    /**
     * 利用虚拟头节点解题
     */
    public static Node.IntNode removeNthFromEnd2(Node.IntNode head, int n) {
        //1、增加头结点
        Node.IntNode dummy = new Node.IntNode(0, head);
        //2、计算链表长度
        int length = 0;
        while (head != null) {
            ++length;
            head = head.next;
        }
        //3、校验入参是否合法
        if (n < 1 || n > length) {
            System.out.println("输入错误，1<n<" + length);
            return new Node.IntNode(-1);
        }
        //4、循环找到目标节点前一个节点
        Node.IntNode cur = dummy;
        for (int i = 1; i < length - n + 1; ++i) {
            cur = cur.next;
        }
        //5、节点删除
        cur.next = cur.next.next;
        Node.IntNode ans = dummy.next;
        //6、返回
        return ans;
    }
    
    /**
     * 利用栈进行解题
     */
    public static Node.IntNode removeNthFromEnd3(Node.IntNode head, int n) {
        //1、增加虚拟头节点
        Node.IntNode dummy = new Node.IntNode(0, head);
        //2、创建stack（栈）
        Deque<Node.IntNode> stack = new LinkedList<Node.IntNode>();
        //3、节点入栈
        Node.IntNode cur = dummy;
        while (cur != null) {
            stack.push(cur);
            cur = cur.next;
        }
        //4、节点出栈
        for (int i = 0; i < n; ++i) {
            stack.pop();
        }
        //5、找到目标节点上一个节点
        Node.IntNode prev = stack.peek();
        //6、删除节点
        prev.next = prev.next.next;
        Node.IntNode ans = dummy.next;
        //7、返回
        return ans;
    }

    /**
     * 利用回溯法后序遍历
     */
    public static Node.IntNode removeNthFromEnd4(Node.IntNode head, int n) {
        int traverse = traverse(head, n);
        if(traverse == n)
            return head.next;
        return head;
    }
    private static int traverse(Node.IntNode node, int n) {
        if(node == null)
            return 0;
        int num = traverse(node.next, n);
        if(num == n)
            node.next = node.next.next;
        return num + 1;
    }

    public static void main(String[] args) {
        Node.IntNode n = Node.getIntNode123456789();
        Node.IntNode res = removeNthFromEnd2(n, 2);
        Node.IntNode curr = res;
        while (curr != null) {
            System.out.println("遍历 n = " + curr.val);
            curr = curr.next;
        }
    }
}