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

一、题目描述

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

示例 :

给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后，链表变为 1->2->3->5.

说明：

给定的 n 保证是有效的。

进阶：

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

二、解题思路

一、递归遍历

1、解题思路

1. 设置全局变量total，index，Nth，，分别代表节点总数，递归坐标，倒数第 n 个节点数。

2. 设置虚拟头节点，并指向head；因为当要删除的节点为第一个节点时，需要一个前驱进行操作。

3. 进行递归遍历，每进入递归函数且改节点存在时total加一。当递归至空节点时，将help复制为节点总数，

4. 寻找到倒第N个节点前驱，即可解答该题啦！满足total==Nth+index即代表该节点为前取，即可进行删除操作。

2、代码

public class Solution{
     //采用递归遍历 至第倒N+1个节点进行删除
    int total = 0;//节点总数
    int index=0;//递归坐标
    int Nth = 0;//被删除的n
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if(head== null||n==0)return head;
        //虚拟头节点(当被删除的为第一个时，需用到前驱节点)
        ListNode dummyNode = new ListNode(-1);
        dummyNode.next= head;
        Nth = n;
        removeNthHelper(dummyNode);
        return dummyNode.next;
    }
    private void removeNthHelper(ListNode head) {
        if(head== null){
            index=total+1;
            return;
        }
        total++;//计算节点总数
        ListNode cur = head.next;
        removeNthHelper(cur);
        index--;//递归节点坐标
        if((index+Nth)==total){//定位至被删节点的前一位
            head.next= cur.next;
        }
    }
}

二、窗口法

1、解题思路

1. 设置虚拟头节点，并指向head；因为当要删除的节点为第一个节点时，需要一个前驱进行操作。
2. 设置双指针p，q，首先将q指针往后移至n+1个节点，使指针p执行p,q组成的窗口的倒第N个节点的前驱。
3. 移动该窗口，直至指针q移至末尾，则指针p指向的即为该链表的倒第N个节点的前驱。即可进行删除操作。

2、代码

public class Solution {

    //双指针法至窗口
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if(head== null||n==0)return head;
        //虚拟头节点(当被删除的为第一个时，需用到前驱节点)
        ListNode dummyNode = new ListNode(-1);
        dummyNode.next= head;
        //双指针 先将两指针距离相隔n+1个，指针q为倒第n个节点的前驱
        ListNode p = dummyNode,q=dummyNode;
        for(int i =0;i<=n;i++)q = q.next;

        //窗口移动，直至移至末尾
        while (q!=null){
            p=p.next;
            q=q.next;
        }

        //此时q指针便是倒第n个节点的前驱
        p.next = p.next.next;
        return dummyNode.next;
    }
}