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

题目链接

给你一个链表，删除链表的倒数第 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]

提示：

• 链表中结点的数目为 sz
• 1 <= sz <= 30
• 0 <= Node.val <= 100
• 1 <= n <= sz

思路

想知道倒数第几个节点必须知道链表的长度。如果想一遍遍历结束那么只能借助快慢指针方法。但是正常快慢指针快指走到终点时慢指针才走完一半，所以这样只能删除后半段的节点。

可以换种思路，快指针走到终点时，既然可以获得链表长度。那么就可以知道要删除节点是处于前半部分还是后半部分，处于后半部分的话让慢指针继续向后遍历即可，如果处于前半部分那么让慢指针从头开始遍历即可。

快慢指针

public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode fast = head;
    ListNode slow = head;
    int length = 1;
    while(fast.next != null && fast.next.next != null){
        fast = fast.next.next;
        slow = slow.next;
        length += 2;
    }
    if(fast.next != null){
        length++;
    }

    int half = length / 2;
    // 慢指针从中间继续后移
    if(half >= n){
        while(half - n > 0){
            slow = slow.next;
            n++;
        }
        slow.next = slow.next.next;
        return head;
    }

    // 慢指针从头开始移动
    ListNode pHead = new ListNode();
    pHead.next = head;
    ListNode cur = pHead;
    while(length - n > 0){
        cur = cur.next;
        n++;
    }
    cur.next = cur.next.next;
    return pHead.next;
}

双指针

要删除倒数第 n 个节点，如果在一次遍历的时候就可以确定删除节点的位置那么就可以直接把该节点移除了。以此为思路可以使用两个指针，right 指针一开始右移 n 位，然后 left 指针指向虚拟头结点 pHead，这样 right 指针和 left 指针就相差 n+1 位，一起右移，当right指针到达终点时，left 指针正好指向 倒数第 n+1 位节点，left 指针的下一位就是要删除的节点。

public ListNode removeNthFromEnd(ListNode head, int n) {
    // 虚拟头结点
    ListNode pHead = new ListNode();
    pHead.next = head;
    ListNode left = pHead;
    ListNode right = head;
    while (right != null) {
        right = right.next;
        if (n > 0) {
            n--;
        } else {
            // 待 right 指针移动 n 位后，left 指针开始移动
            left = left.next;
        }
    }
    // 删除left指针的下一个节点
    left.next = left.next.next;
    return pHead.next;
}