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

题目: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

思路

1. 计算链表的长度。
2. 当n等于链表长度时直接删除第一个结点并返回。
3. 删除倒数第n个节点。

• 时间复杂度:O(n)
• 空间复杂度:O(1)

代码

public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode result = new ListNode(0);
    result.next = head;
    ListNode current = head;
    int listSize = 1;
    // 计算链表的长度
    while (current.next != null) {
        current = current.next;
        listSize++;
    }
    // 当n等于链表长度时直接删除第一个结点并返回
    if (n == listSize) {
        return head.next;
    }
    current = head;
    // 删除倒数第n个节点
    if (current.next != null) {
        for (int i = 0; i < listSize - n - 1; i++) {
            current = current.next;
        }
        current.next = current.next.next;
    }
    return result.next;
}