题目

思路

常规思路：对整个链表进行遍历，得到链表的长度L，然后再从头开始遍历，遍历到L - n + 1个位置，就是要删除的倒数第n个节点，时间复杂度为O（n）

双指针：双指针思路就是通过两个指针，一个先移动n个节点，然后两个同时移动，当先移动的那个节点走到末尾时，说明链表已遍历结束，而后移动的那个节点的下一个节点就是我们要删除的倒数第n个节点（两个指针之间的距离为n）

代码实现

package list;

import java.util.Scanner;

public class RemoveNthFromEnd {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        String[] split = s.substring(1, s.length() - 1).split(",");

        int[] nums = new int[split.length];
        for (int i = 0; i < nums.length; i++) {
            nums[i] = Integer.parseInt(split[i]);
        }
        int n = sc.nextInt();
        ListNode list = ListUtil.getListFromArray(nums);
        ListNode out = removeNthFromEnd(list, n);

        ListUtil.listToString(out);
    }

    public static ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode pre = new ListNode(-1);
        pre.next = head;
        ListNode left = pre;
        ListNode right = pre;
        //右指针先走n步
        while (n > 0) {
            right = right.next;
            n--;
        }
        //左右指针一起走
        while (right.next != null) {
            left = left.next;
            right = right.next;
        }
        //删除倒数第n个节点
        left.next = left.next.next;

        return pre.next;
    }
}