删除链表的倒数第n个节点

题目：

思路：

由于这是一个链表，所以我们一般只能获取到一个头结点，然而其他信息我们不确定。所以可以采用双指针的方法。

思路一，利用一个指针获取整个链表元素的总数，利用总数减去目标数，所以我们可以确定要删除的位置。

思路二，利用一个指针先走出目标数目，然后两个指针一起走，那么先走的指针走完时，第二个指针恰好会停在目标元素上。

代码示例：

public class Solution4 {

    public static void main(String[] args) {

        ListNode head = new ListNode(1);

        ListNode node2 = new ListNode(2);

        ListNode node3 = new ListNode(3);

        ListNode node4 = new ListNode(4);

        ListNode node5 = new ListNode(5);

        head.next = node2;

//        node2.next = node3;

//        node3.next = node4;

//        node4.next = node5;

        int n = 1;

        ListNode result = removeNthFromEnd(head, n);

        System.out.println(result);

        OutPutLinkedList(result);

    }

    /**

     * 方案2，用双指针，一个先走一定的步数，然后一起走，某一个先抵达就停止

     *

     * @param head ListNode类

     * @param n    int整型

     * @return ListNode类

     */

    public static ListNode removeNthFromEnd(ListNode head, int n) {

        if (head == null || n == 0)

            return head;

        ListNode p1 = head;

        ListNode p2 = head;

        //p2先走n步

        for (int i = 0; i < n; i++) {

            p2 = p2.next;

        }

        //当指针p2走完n步以后，让指针p2和p1同时向前走，直到p2走到最后一个节点，即p2->next=NULL

        // 整个过程p2和p1之间相隔n-1个节点

        while (p2 != null && p2.next != null) {

            p2 = p2.next;

            p1 = p1.next;

        }

        //如果是头结点，就将头结点指向下一位

        if (p2 == null) {

            head = head.next;

        } else {

            //删除元素

            p1.next = p1.next.next;

        }

        return head;

    }

    /**

     * 方案1，先获取总数，然后通过运算得出

     *

     * @param head ListNode类

     * @param n    int整型

     * @return ListNode类

     */

    public static ListNode removeNthFromEnd1(ListNode head, int n) {

        if (head == null || n == 0)

            return head;

        int num = 1;

        ListNode p1 = head;

        ListNode p2 = head;

        //想算出元素的总数

        while (p1.next != null) {

            p1 = p1.next;

            num++;

        }

        //判断是第几个节点

        int index = num - n + 1;

        //总数减去倒数的数n，就是要遍历的位置了

        for (int i = 1; i < index - 1; i++) {

            p2 = p2.next;

        }

        //如果是头结点，就将头结点指向下一位

        if (index == 1) {

            head = head.next;

        } else {

            //删除元素

            p2.next = p2.next.next;

        }

        return head;

    }

    /**

     * 打印链表，用于输出查看

     *

     * @param head

     */

    public static void OutPutLinkedList(ListNode head) {

        ListNode temp = head;

        while (null != temp) {

            System.out.print(temp.val);

            if (null != temp.next) {

                System.out.print(" -> ");

            }

            temp = temp.next;

        }

        System.out.println();

    }

}

class ListNode {

    int val;

    ListNode next;

    ListNode(int x) {

        val = x;

        next = null;

    }

}