leetcode 19. 删除链表的倒数第 N 个结点

一、题目

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

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

二、解法

常规思路：先扫描一次，得到链表的长度 \(len\) ，然后扫描得到 \(len-n\) 个节点即可。

如果要想一趟扫描实现，思路是 快慢指针。
快指针 \(fast\) 比慢指针 \(slow\) 快 \(n\) 个节点，然后当 \(fast\) 遍历到末尾时，慢指针的位置即为要删除的位置。

小技巧：这种链表删除的题目，通常需要用一个虚拟头结点 \(dummy\) ，是为了避免讨论删除头结点带来的额外代码。

/**
 * 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 dummy=new ListNode(0,head);
        ListNode slow=dummy,fast=dummy;
        for(int i=0;i<n;++i){
            fast=fast.next;
        }

        while(fast.next!=null){
            fast=fast.next;
            slow=slow.next;
        }

        slow.next=slow.next.next;
        return dummy.next;  
    }
}

leetcode 19. 删除链表的倒数第 N 个结点

原文：https://www.cnblogs.com/livingsu/p/14880446.html