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

题目描述

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

示例:

输入: 1->2->3->4->5, n = 2
输出: 1->2->3->5

解题思路

使用双指针的方法来找到倒数第 n 个节点，然后删除该节点。

解题步骤

1. 使用两个指针 fast 和 slow，初始时都指向链表的头节点。
2. 先将 fast 指针向前移动 n+1 步。
3. 然后，同时移动 fast 和 slow 指针，直到 fast 指针到达链表末尾。
4. 此时，slow 指针指向倒数第 n+1 个节点。
5. 将 slow 指针的下一个节点删除，即将 slow.next 指向 slow.next.next。
6. 返回头节点。

C#代码实现

public ListNode RemoveNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode fast = dummy;
    ListNode slow = dummy;

    // 先将 fast 指针向前移动 n+1 步
    for (int i = 0; i <= n; i++) {
        fast = fast.next;
    }

    // 同时移动 fast 和 slow 指针，直到 fast 到达链表末尾
    while (fast != null) {
        fast = fast.next;
        slow = slow.next;
    }

    // 删除倒数第 n 个节点
    slow.next = slow.next.next;

    return dummy.next;
}

C代码实现

struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
    struct ListNode* dummy = malloc(sizeof(struct ListNode));
    dummy->next = head;
    struct ListNode* fast = dummy;
    struct ListNode* slow = dummy;

    // 先将 fast 指针向前移动 n+1 步
    for (int i = 0; i <= n; i++) {
        fast = fast->next;
    }

    // 同时移动 fast 和 slow 指针，直到 fast 到达链表末尾
    while (fast != NULL) {
        fast = fast->next;
        slow = slow->next;
    }

    // 删除倒数第 n 个节点
    struct ListNode* temp = slow->next;
    slow->next = slow->next->next;
    free(temp);

    return dummy->next;
}

时间复杂度和空间复杂度

• 时间复杂度：O(n)，其中 n 是链表的长度。两个指针分别遍历链表一次。
• 空间复杂度：O(1)。除了常数级别的变量，算法的空间复杂度是常数级别的。