本文主要是介绍LeetCode链表篇【删除链表的倒数】，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

力扣题目链接(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;
    }
}

这篇关于LeetCode链表篇【删除链表的倒数】的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！