力扣题目链接(opens new window)

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

进阶：你能尝试使用一趟扫描实现吗？

示例 1：

输入：head = [1,2,3,4,5], n = 2 输出：[1,2,3,5] 示例 2：

输入：head = [1], n = 1 输出：[] 示例 3：

输入：head = [1,2], n = 1 输出：[1]

 

正解

1)两次历遍：先手历遍一次获得size大小，在结合倒数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) {

        ListNode virtual = new ListNode(0);
        virtual.next = head;
        ListNode temp=virtual;
        int size = 0;
        int index;
        ListNode ret=virtual;
        while (temp.next != null) {
            size++;
            temp=temp.next;
        }
        index = size - n + 1;
        for (int i = 0; i < index-1; i++) {
            virtual = virtual.next;
        }

        if (virtual.next != null && virtual.next.next != null) {
            virtual.next =virtual.next.next;
        } else {
            virtual.next = null;
        }

        return ret.next;
    }
}

2）双指针一次历遍：如果要删除倒数第n个节点，让fast移动n步，然后让fast和slow同时移动，直到fast指向链表末尾。删掉slow所指向的节点就可以了。

• 定义fast指针和slow指针，初始值为虚拟头结点，如图：

• fast首先走n + 1步 ，为什么是n+1呢，因为只有这样同时移动的时候slow才能指向删除节点的上一个节点（方便做删除操作），如图： 

  

• fast和slow同时移动，之道fast指向末尾，如题： 

  

• 删除slow指向的下一个节点，如图： 

  

/**
 * 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) {

        ListNode virtual = new ListNode(0);
        virtual.next = head;
        ListNode fast=virtual;
        ListNode low=virtual;
        int size=0;
        while (fast.next!=null){
            fast=fast.next;
            size++;
            if(size>n){
                low=low.next;
            }
        }
        if(low.next.next!=null){
            low.next=low.next.next;
        }else {
            low.next=null;
        }       
        return virtual.next;
    }
}