思路

单向链表的特点就是只能往一个方向走,如果需要知道某个点的位置,单纯通过遍历的方式,一次是无法完成的.
基于这个前提,必须引入其他工具,最容易想到的工具就是使用多个指针,又因为单链表的单向性,这里的指针
也叫快慢指针.

代码框架

1. dummy节点指向头节点, cur初始化为dummy指针
2. 快,慢指针f,s分别都初始化为head
3. f指针先走n步
4. f走到链表结尾的同时, s指针保持前移
5. s停止的位置正好是要删除的节点, 因此需要使cur指针指向s节点
6. cur.next = cur.next.next 完成删除操作

java

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if(head == null) return head;

        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode cur = dummy;

        ListNode f = head;
        ListNode s = head;
        while(n-- > 0){
            f = f.next;
        }

        while(f != null){
            cur = cur.next;
            s = s.next;
            f = f.next;
        }

        if(cur.next != null) cur.next = cur.next.next;

        return dummy.next;
    }
}