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

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

示例：

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

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

说明：

给定的 n 保证是有效的。

进阶：

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

解题思路1：遍历获取链表长度L，(L - N)即为需删除节点的前驱节点，将这个节点指向需删除节点的后驱节点。

时间复杂度为 O(L)，空间复杂度为 O(1)

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        int length = 0;
        ListNode del = head;
        while (del != null) {
            length++;
            del = del.next;
        }
        length = length - n;
        del = dummy;
        while (length > 0) {
            length--;
            del = del.next;
        }
        del.next = del.next.next;
        return dummy.next;
    }
}

解题思路2：双指针遍历，快慢指针，快指针先走 n 步，然后双指针同时出发，当快指针指向 null 时，慢指针恰好到需删除指针的前驱节点。

时间复杂度为 O(L)，空间复杂度为 O(1)

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode slow = dummy, fast = dummy;
        while (n != 0) {
            fast = fast.next;
            n--;
        }
        while (fast.next != null) {
            slow = slow.next;
            fast = fast.next;
        }
        slow.next = slow.next.next;
        return dummy.next;
    }
}

Tips：dummy node 翻译为哑节点或哨兵节点，用于避免一些边界情况，例如空链表和只有一个节点的单链表需要增加或删除。