LeetCode- 19 删除链表的倒数第N个节点

题目地址

https://leetcode.cn/problems/remove-nth-node-from-end-of-list/description/

参考实现

 /**
     * Definition for singly-linked list.
     * public class ListNode {
     * int val;
     * ListNode next;
     * ListNode() {}
     * ListNode(int val) { this.val = val; }
     * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */
    /**
     * 通过链表长度 进行处理
     *
     * @param head
     * @param n
     * @return
     */
    public static ListNode removeNthFromEnd1(ListNode head, int n) {
        ListNode dumny = new ListNode(0, head);
        ListNode current = dumny;
        for (int i = 1; i < getLenth1(head) - n + 1; i++) {
            current = current.next;
        }
        //执行删除
        current.next = current.next.next;
        return dumny.next;

    }

    /**
     * 获取链表大小
     *
     * @param head
     * @return
     */
    public static int getLenth1(ListNode head) {
        int length = 0;
        while (head != null) {
            head = head.next;
            length++;
        }

        return length;
    }

    /**
     * 利用栈特性处理
     *
     * @param head
     * @param n
     * @return
     */
    public static ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dumny = new ListNode(0, head);
        Deque<ListNode> stack = (Deque<ListNode>) new LinkedList<ListNode>();
        ListNode current = dumny;
        while (current != null) {
            stack.push(current);
            current = current.next;
        }

        for (int i = 0; i < n; i++) {
            stack.pop();
        }

        ListNode peek = stack.peek();
        peek.next = peek.next.next;
        return dumny.next;
    }

    /**
     * 双指针处理
     *
     * @param head
     * @param n
     * @return
     */
    public static ListNode removeNthFromEnd3(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        ListNode first = head;
        ListNode second = dummy;
        for (int i = 0; i < n; i++) {
            first = first.next;
        }
        while (first != null) {
            first = first.next;
            second = second.next;
        }
        second.next = second.next.next;
        return dummy.next;
    }