删除链表倒数第n个节点

/**

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

 * }

 */

class Solution {

    /**

     * 计算出链表长度，推算出需要删除正序的某个节点。

     */

    public ListNode removeNthFromEnd(ListNode head, int n) {

        // 计算出链表长度

        int length = 0;

        ListNode temp = head;

        while (temp != null){

            length++;

            temp = temp.next;

        }

        temp = new ListNode(0, head);

        // 正序的第 length 个的节点需要别删除

        length = length - n;

        // 如果是开头，则删除头结点

        if (length == 0) return head.next;

        // 循环达到第 length 个节点

        while (temp != null && length >= 0){

            // 删除这个节点

            if (length == 0){

                temp.next = temp.next.next;

                return head;

            }

            length--;

            temp = temp.next;

        }

        return null;

    }

}

/**

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

 * }

 */

class Solution1 {

    /**

     * 快慢指针实现

     * 当快指针先移动 n 次之后再移动满指针，

     * 快指针移动到最后的时候，

     * 满指针指向的节点就是需要删除的节点，

     */

    public ListNode removeNthFromEnd(ListNode head, int n) {

        // 快指针

        ListNode quick = head;

        // 慢指针

        ListNode slow = new ListNode(0, head);

        // 移动快指针

        while (quick != null){

            // 当快指针移动 n 次之后，在移动满指针，当快指针达到最后时，满指针就是倒数第 n 个节点

            if (n <= 0) slow = slow.next;

            quick = quick.next;

            n--;

        }

        // 当满指针未移动时，说明是需要删除头节点

        if (slow.next == head) return head.next;

        // 删除倒数第 n 节点

        slow.next = slow.next.next;

        return head;

    }

}