1. 原题链接

2. 题目要求

给出一个链表，请删除倒数第n个结点并返回头节点

注意：给出的n总在合法范围内；只用一次遍历；

3. 解题思路

删除倒数第n个结点，正着数即删除从表头结点开始的第L-n+1个结点。创建一个表头结点来指向头结点。

思路一：使用两次遍历。第一次遍历得到链表的长度，第二遍历删除第L-n+1个结点。

思路二：使用一次遍历。使用两个指针first和second，开始时first和second都指向头结点head。first指针先到达正数第n个结点，second指针不动。然后两个指针同步向后移动，保持两个指针之间的gap为n。当first.next==null时，second指针指向倒数第n个结点。

4. 代码实现

 

package com.huiAlex;import java.util.List;/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */public class RemoveNthNodeFromEndofList19 {    public static void main(String[] args) {        ListNode l1 = new ListNode(1);        ListNode l2= new ListNode(2);        ListNode l3 = new ListNode(3);        ListNode l4= new ListNode(4);        ListNode l5 = new ListNode(5);        ListNode l6= new ListNode(6);        l1.next=l2;        l2.next =l3;        l3.next=l4;        l4.next=l5;        l5.next=l6;        ListNode ls = RemoveNthNodeFromEndofList19.removeNthFromEnd(l1,3);        ListNode ls2 = l1.next.next.next;        System.out.println("头结点："+ls.val);   // Expected：1        System.out.println("删除nth结点后，其前驱结点的后继结点"+ls2.val);  // Expected：5    }    // 思路二代码实现    public static ListNode removeNthFromEnd(ListNode head, int n){        ListNode headPointer = new ListNode(0);        headPointer.next = head;        ListNode first = head,second = head;        for(int i =0;i
     
       0) {  // 第二次遍历找到倒数第n个结点            length--;            first = first.next;        }        first.next = first.next.next;  // 删除倒数第n个结点        return headPointer.next;    }    public static class ListNode {        int val;        ListNode next;        ListNode(int x) {            val = x;        }    }}