题解 | #删除链表的倒数第n个节点#

前置知识

需要先了解找倒数第k个结点的方法
这里附上“BM8-链表中倒数最后k个结点”的题解：附图解

思路 （以下用k代表n）

• 找到倒数第k+1个结点：now
• 将倒数第k+1个结点指向倒数第k-1个结点，即now.next=now.next.next
• 将倒数第k个结点赋值为null

边界条件讨论

• 如果k=链表长度，则为删除第一个结点，倒数第k+1个结点为null，则返回倒数第k-1个结点
• 如果k大于链表长度（不可能出现，题目保证n有效）
• 如果k=1，则删除最后一个结点，此种边界情况可归并到普通思路中。

符号说明

• now用于遍历链表（迭代器）
• last用于记录now的上一个结点
• box用于记录倒数k+1个结点

public ListNode removeNthFromEnd (ListNode head, int n) {
        if(head==null) return null;
        ListNode now=head;
        ListNode[] box=new ListNode[n+1];
        int i=0;
        //维护box，跳出循环时box[i]为倒数第k+1个结点
        while(now!=null){
            box[i]=now;
            if(i==n) i=0;
            else i++;
            now=now.next;
        }
        //如果k=链表长度，则倒数第k个结点为第一个结点，倒数第k+1个结点不存在，即为null
        if(box[i]==null){
            return head.next;
        }
        //如果k=1，倒数第k+1个结点为box[i]，倒数第k个结点为box[0]
        if(i==n){
            box[i].next=box[0].next;
            box[0]=null;
        }
        //k小于链表长度
        else{
            box[i].next=box[i+1].next;
            box[i+1]=null;  
        }
        return head;
    }