力扣:删除链表的倒数第N个节点（移除链表元素力扣）

package com.company.链表;

/**
 * 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
 */
public class 删除链表中的倒数第N个节点 {

    public static void main(String[] args) {

    }

    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; }
    }


    /**
     * 双指针解法 (如果下列步骤还是不懂的话，可直接画一个图便于理解)
     * 1.定义两个指针，快指针和慢指针
     * 2.快指针先走N步,就到了第N+1个节点
     * 3.快指针和慢指针一起一步一步继续往后走
     * 4.当快指针到了最后一个节点，则慢指针的位置就是倒数第N个节点的前一个节点
     * 5.把前一个节点的值指向后一个的后一个节点就把倒数第N个节点删除了
     * 注意临界点
     * @param head
     * @param n
     * @return
     */
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode fast = head;
        ListNode slow = head;
        for (int i = 0; i < n; i++) {
            fast = fast.next;
        }
        // 注意:临界点 1.如果fast为空,则删除的就是头结点，则返回投节点的下一个节点
        if (fast == null) return head.next;
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;
        return head;
    }

    /**
     * 递归解法
     * 计算链表长度的递归其实可以把它看做是从后往前计算，
     * 当计算的长度是n的时候就表示遍历到了倒数第n个节点了，
     * 这里只要求出倒数第n+1个节点
     * @param head
     * @param n
     * @return
     */
    public ListNode removeNthFromEnd1(ListNode head, int n) {
        int len = length(head,n); 
        // 链表总长度是n，则删除头节点        
        if (len == n) {
            return head.next;
        }
        return head;
    }

    private static int length(ListNode node, int n) {
        if (node == null) return 0;
        int len = length(node.next,n) + 1;
        if (len == n+1) {
            node.next = node.next.next;
        }
        return len;
    }

}