leetcode 021:删除链表的倒数第 N 个结点

LCR 021. 删除链表的倒数第 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]

struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
    // 创建一个哑节点，其next指向头节点，方便处理边界情况
    struct ListNode* dummy = malloc(sizeof(struct ListNode));
    dummy->val = 0, dummy->next = head;
    
    // 初始化两个指针，first指向链表头部，second指向哑节点
    struct ListNode* first = head;
    struct ListNode* second = dummy;
    
    // 首先移动first指针n个节点，这样first和second之间的距离就是n
    for (int i = 0; i < n; ++i) {
        first = first->next;
    }
    
    // 如果first已经到达链表末尾，说明需要删除的是头节点
    if (first == NULL) {
        dummy->next = head->next; // 哑节点的next指向头节点的后继节点
        free(head); // 释放头节点
        struct ListNode* ans = dummy->next; // 返回新的头节点
        free(dummy); // 释放哑节点
        return ans;
    }
    
    // 然后移动first和second指针，直到first到达链表末尾
    while (first) {
        first = first->next; // first继续向后移动
        second = second->next; // second也向后移动，保持first和second之间的距离为n
    }
    
    // 此时second指向要删除节点的前一个节点
    // 删除操作：将second的next指向要删除节点的后继节点
    second->next = second->next->next;
    
    // 从哑节点的next获取更新后的链表头节点
    struct ListNode* ans = dummy->next;
    
    // 释放哑节点，此时链表已经通过哑节点和删除操作更新，不再需要哑节点
    free(dummy);
    
    // 返回更新后的链表头节点
    return ans;
    

    
}